Cod sursa(job #3260115)

Utilizator vladsoartavlad sofronea vladsoarta Data 30 noiembrie 2024 10:40:05
Problema Gardieni Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>
#define int long long
using namespace std;
ifstream cin("gardieni.in");
ofstream cout("gardieni.out");

vector<tuple<int,int,bool>>events;
set<pair<int,int>>s;

int vals[60001],n,t,i,l,r,val;

int32_t main()
{
    cin>>n>>t;
    for(i=1;i<=n;i++)
    {
        cin>>l>>r>>val;
        events.push_back(make_tuple(l,i,0));
        events.push_back(make_tuple(r+1,i,1));
        vals[i] = val;
    }
    sort(events.begin(),events.end());

    int j=0;
    while(get<0>(events[j]) == 1&&j<events.size())
        s.insert(make_pair(vals[get<1>(events[j])],get<1>(events[j]))),j++;

    int currT = 1;
    long long sfin=0;
    while(j<events.size())
    {
      sfin+=s.begin()->first * (get<0>(events[j])-currT);
      currT = get<0>(events[j]);
      while(currT == get<0>(events[j])&&j<events.size())
      {
          if(!get<2>(events[j])){
            s.insert(make_pair(vals[get<1>(events[j])],get<1>(events[j])));
          }
          else{
            s.erase(make_pair(vals[get<1>(events[j])],get<1>(events[j])));
          }
          j++;
      }
    }
    cout<<sfin;

    return 0;
}