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>
#define f0(i, n) for(int i=(0); i<n; i++)
#define f1(i, n) for(int i=(1); i<=n; i++)
using namespace std;
typedef long long ll;
const int N = 200002;
struct data{
int x, id;
bool operator <(data g){
return x < g.x;
}
} a[N], b[N];
int n, k, t[N], answer[N];
void up(int node, int l, int r, int i, int val){
if(r < i || l > i) return ;
if(l==r){
t[node] = val;
return ;
}
int m = (l + r)/2;
up(node*2, l, m, i, val);
up(node*2+1, m + 1, r, i, val);
t[node] = max(t[2*node], t[2*node+1]);
}
int get2(int node, int l, int r, int i, int j){
if(r < i || l > j) return 0;
if(l >= i && r <= j) return t[node];
int m = (l + r)/2;
return max(get2(node*2, l, m, i, j), get2(node*2+1, m + 1, r, i, j));
}
void update(int x, int val){
up(1, 1, k, x, val);
}
int get1(int x, int y){
return get2(1, 1, k, x, y);
}
int Ans(int x){if(x==1) return 2;return 1;}
main(){
ios_base::sync_with_stdio(0);
cin >> n >> k;
f1(i, n){
cin >> a[i].x >> b[i].x;
b[i].id = a[i].id = i;
}
f1(i, k){
int u; cin >> u;
update(i, u);
}
vector <pair <int, int> > save;
f1(i, n){
/// assume a[i] could be ans[1]
/// find 1 and 2
while(save.size()) save.pop_back();
int k1 = k, k2 = k;
while(1){
int p1, p2;
int l = 1, r = k1, ans = 0;
while(l <= r){
int mid = (l + r)/2;
if(get1(mid, k1) >= a[i].x) ans = mid, l = mid + 1;
else r = mid - 1;
} p1 = ans;
l = 1, r = k2, ans = 0;
while(l <= r){
int mid = (l + r)/2;
if(get1(mid, k2) >= b[i].x) ans = mid, l = mid + 1;
else r = mid - 1;
} p2 = ans;
save.push_back(make_pair(p1, p2));
if(p1 != p2) break;
if(p1==0) break;
k1 = p1 - 1, k2 = p2 - 1;
}
int y = 2; /// now i belong to Ans(2)
if(save.size() == 1){
if(save[0].first > save[0].second) answer[i] = Ans(1);
else answer[i] = Ans(2);
}
else{
for(int j = save.size() - 1; j >= 0; j--){
if(min(save[j].first, save[j].second)){
if(save[j].first==save[j].second){
if(y==2) y = 1;
else y = 2;
}
else{
if(save[j].first > save[j].second){
y = 1;
}
else{
y = 2;
}
}
}
}
answer[i] = Ans(y);
}
}
ll res = 0;
f1(i, n){
if(answer[i]==2) res += ll(b[i].x);
else res += ll(a[i].x);
}
cout << res;
}
Compilation message (stderr)
fortune_telling2.cpp:45:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
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... |