Submission #49616

#TimeUsernameProblemLanguageResultExecution timeMemory
49616mra2322001Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
130 ms5688 KiB
#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, pos[N], ans[N], h3[N], h4[N]; pair <int, int> h1[N], h2[N]; vector <vector <int> > t1, t2; void up(int x, int i, int id){ for(x; x > 0; x -= (x & -x)){ if(id==1){ if(i > h1[x].first){ h1[x].second = h1[x].first; h1[x].first = i; } else if(i == h1[x].first){ h1[x].second = i; } else{ if(i > h1[x].second){ h1[x].second = i; } } h3[x] = min(h3[x], i); } else{ if(i > h2[x].first){ h2[x].second = h2[x].first; h2[x].first = i; } else if(i == h2[x].first){ h2[x].second = i; } else{ if(i > h2[x].second){ h2[x].second = i; } } h3[x] = min(h4[x], i); } } } int get1(int x, int id){ int res = 0; for(x; x <= n; x += (x & -x)){ if(id==1) res = max(res, h1[x].first); else res = max(res, h2[x].first); } return res; } int get2(int x, int y){ int res = 0; for(x; x <= n; x += (x & -x)){ if(h2[x].first < y) res = max(res, h2[x].first); if(h2[x].second < y) res = max(res, h2[x].second); } return res; } int get3(int x){ int res = 1e9; for(x; x <= n; x += (x & -x)) res = min(res, h3[x]); return res; } main(){ ios_base::sync_with_stdio(0); cin >> n >> k; t1.resize(n + 1); t2.resize(n + 1); memset(h3, 0x3f3f3f, sizeof(h3)); memset(h4, 0x3f3f3f, sizeof(h4)); f1(i, n){ cin >> a[i].x >> b[i].x; b[i].id = a[i].id = i; } sort(a + 1, a + n + 1); sort(b + 1, b + n + 1); f1(i, k){ int x; cin >> x; data g = {x + 1, 0}; int ki = lower_bound(a + 1, a + n + 1, g) - a; --ki; t1[ki].push_back(i); ki = lower_bound(b + 1, b + n + 1, g) - b; --ki; t2[ki].push_back(i); } for(int i = n; i >= 1; i--){ for(auto x:t1[i]){ up(i, x, 1); } for(auto x:t2[i]){ up(i, x, 2); } } f1(i, n){ pos[b[i].id] = i; } f1(i, n){ int k = a[i].id; int u = get1(i, 1); if(u==0) ans[k] = 1; else{ int v = get1(pos[k], 2); if(v > u) ans[k] = 1; else if(v==u){ int tr = get2(pos[k], v); if(tr > N) tr = 0; int rt = get3(i); if(tr==0){ ans[k] = 2; continue; } if(rt==u){ ans[k] = 2; continue; } if(tr > rt && tr < u){ ans[k] = 2; continue; } ans[k] = 1; } else{ ans[k] = 2; } } } ll res = 0; f1(i, n){ if(ans[a[i].id]==1){ res += ll(a[i].x); } else{ res += ll(b[pos[a[i].id]].x); } } cout << res; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'void up(int, int, int)':
fortune_telling2.cpp:20:10: warning: statement has no effect [-Wunused-value]
     for(x; x > 0; x -= (x & -x)){
          ^
fortune_telling2.cpp: In function 'int get1(int, int)':
fortune_telling2.cpp:56:10: warning: statement has no effect [-Wunused-value]
     for(x; x <= n; x += (x & -x)){
          ^
fortune_telling2.cpp: In function 'int get2(int, int)':
fortune_telling2.cpp:65:10: warning: statement has no effect [-Wunused-value]
     for(x; x <= n; x += (x & -x)){
          ^
fortune_telling2.cpp: In function 'int get3(int)':
fortune_telling2.cpp:74:10: warning: statement has no effect [-Wunused-value]
     for(x; x <= n; x += (x & -x)) res = min(res, h3[x]);
          ^
fortune_telling2.cpp: At global scope:
fortune_telling2.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...