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 <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define int long long int
const int INF = 2000000000000000000;
int minVal[200010], maxVal[200010], maxSide[200010];
int queries[200010];
int resp[200010];
vector<int> cardsQueries[200010];
map<int, int> cc;
int segEntre[2000010], segMaior[2000010];
void updateSegEntre(int pseg, int ini, int fim, int p, int val){
if(p<ini || p>fim) return;
if(ini==fim){
segEntre[pseg] = val;
return;
}
int m = (ini + fim)/2;
int l = 2*pseg;
int r = 2*pseg + 1;
updateSegEntre(l, ini, m, p, val);
updateSegEntre(r, m + 1, fim, p, val);
segEntre[pseg] = max(segEntre[l], segEntre[r]);
}
int querySegEntre(int pseg, int ini, int fim, int qini, int qfim){
if(qini>fim || qfim<ini) return 0;
if(qini<=ini && fim<=qfim) return segEntre[pseg];
int m = (ini + fim)/2;
int l = 2*pseg;
int r = 2*pseg + 1;
return max(querySegEntre(l, ini, m, qini, qfim), querySegEntre(r, m + 1, fim, qini, qfim));
}
void updateSegMaior(int pseg, int ini, int fim, int p){
if(p<ini || p>fim) return;
if(ini==fim){
segMaior[pseg]++;
return;
}
int m = (ini + fim)/2;
int l = 2*pseg;
int r = 2*pseg + 1;
updateSegMaior(l, ini, m, p);
updateSegMaior(r, m + 1, fim, p);
segMaior[pseg] = segMaior[l] + segMaior[r];
}
int querySegMaior(int pseg, int ini, int fim, int qini, int qfim){
if(qini>fim || qfim<ini) return 0;
if(qini<=ini && fim<=qfim) return segMaior[pseg];
int m = (ini + fim)/2;
int l = 2*pseg;
int r = 2*pseg + 1;
return querySegMaior(l, ini, m, qini, qfim) + querySegMaior(r, m + 1, fim, qini, qfim);
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(0);
int n, q; cin>>n>>q;
vector<int> aux;
for(int i=1;i<=n;i++){
int ai, bi; cin>>ai>>bi;
minVal[i] = min(ai, bi);
maxVal[i] = max(ai, bi);
if(ai<bi) maxSide[i] = 1;
aux.pb(ai);
aux.pb(bi);
}
for(int i=1;i<=q;i++){
int ti; cin>>ti;
queries[i] = ti;
aux.pb(ti);
}
sort(aux.begin(), aux.end());
int newVal = 1;
for(int i=0;i<(int)aux.size();i++){
if(cc[aux[i]]==0){
cc[aux[i]] = newVal;
newVal++;
}
}
int maxSeg = newVal - 1;
//cout<<maxSeg<<"\n";
for(int i=1;i<=q;i++) updateSegEntre(1, 1, maxSeg, cc[queries[i]], i);
for(int i=1;i<=n;i++){
int p = querySegEntre(1, 1, maxSeg, cc[minVal[i]], cc[maxVal[i]] - 1);
//cout<<i<<" "<<p<<"\n";
if(p==0 && maxSide[i]==1) resp[i]++;
cardsQueries[p].pb(i);
}
for(int i=q;i>=0;i--){
for(int j=0;j<(int)cardsQueries[i].size();j++){
int qtdMaior = querySegMaior(1, 1, maxSeg, cc[maxVal[cardsQueries[i][j]]], maxSeg);
resp[cardsQueries[i][j]] += qtdMaior;
//cout<<i<<" "<<cardsQueries[i][j]<<" "<<qtdMaior<<"\n";
}
if(i>0) updateSegMaior(1, 1, maxSeg, cc[queries[i]]);
}
int soma = 0;
for(int i=1;i<=n;i++){
//cout<<i<<" "<<resp[i]<<"\n";
if((resp[i]%2)==0) soma += maxVal[i];
else soma += minVal[i];
}
cout<<soma<<"\n";
return 0;
}
Compilation message (stderr)
fortune_telling2.cpp:64:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
64 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |