This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t[600000][2];
int mam[600000][2];
map<int,int> numeracja;
priority_queue<int> spojne[600000];
set<pair<int,pair<int,int> > > secik;
priority_queue<pair<int,int> > kolejka;
void mergee(int gdzie)
{
auto it=secik.find({t[gdzie][1],{t[gdzie][0],gdzie}});
it++;
if(it==secik.end())
{
secik.erase({t[gdzie][1],{t[gdzie][0],gdzie}});
return;
}
int kto=(*it).second.second;
if(spojne[gdzie].size()<spojne[kto].size())
{
while(!spojne[gdzie].empty())
{
int x=spojne[gdzie].top();
spojne[gdzie].pop();
spojne[kto].push(x);
}
if(spojne[kto].size())
kolejka.push({spojne[kto].top()-t[kto][0],kto});
}
else{
while(!spojne[kto].empty())
{
int x=spojne[kto].top();
spojne[kto].pop();
spojne[gdzie].push(x);
}
swap(spojne[kto],spojne[gdzie]);
if(spojne[kto].size())
kolejka.push({spojne[kto].top()-t[kto][0],kto});
}
secik.erase({t[gdzie][1],{t[gdzie][0],gdzie}});
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n,m,o,x,y,z;
cin>>n>>m>>o;
vector<pair<int,pair<int,int> > > Q2;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
t[i][0]=x;
t[i][1]=y;
Q2.push_back({y,{x,i}});
secik.insert({y,{x,i}});
}
vector<pair<int,int> > Q;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
mam[i][0]=x;
mam[i][1]=y;
Q.push_back({y,x});
}
sort(Q.begin(),Q.end());
sort(Q2.begin(),Q2.end());
int patrze=0;
for(int i=0;i<Q.size();i++)
{
while(Q2[patrze].first<Q[i].first)
patrze++;
spojne[Q2[patrze].second.second].push(Q[i].second);
}
for(int i=1;i<=n;i++)
{
if(spojne[i].size()==0)
continue;
kolejka.push({spojne[i].top()-t[i][0],i});
}
int wynik=0;
for(int i=1;i<=o;i++)
{
auto para=kolejka.top();
kolejka.pop();
while(spojne[para.second].size()==0 || para.first!=spojne[para.second].top()-t[para.second][0])
{
para=kolejka.top();
kolejka.pop();
}
wynik+=para.first;
int gdzie=para.second;
spojne[gdzie].pop();
mergee(gdzie);
}
cout<<wynik;
return 0;
}
Compilation message (stderr)
hot.cpp: In function 'int32_t main()':
hot.cpp:77:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<Q.size();i++)
| ~^~~~~~~~~
hot.cpp:55:19: warning: unused variable 'z' [-Wunused-variable]
55 | int n,m,o,x,y,z;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |