Submission #930246

#TimeUsernameProblemLanguageResultExecution timeMemory
930246vjudge1Fortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
4 ms10840 KiB
//Be Name KHODA #pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pp pop_back #define lb lower_bound #define ub upper_bound #define cl clear #define bg begin #define arr(x) array<int , x> #define endl '\n' int n , q; vector<arr(2)> a; vector<int> ops; vector<int> seg[400001]; int seginf[400001][2]; void buildSeg(int l = 0 , int r = q - 1 , int i = 1){ seginf[i][0] = l , seginf[i][1] = r; if(l == r) seg[i].pb(ops[l]); else{ int c = (r + l - 1) >> 1; buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1); seg[i].resize(r - l + 1); merge(seg[i << 1].bg() , seg[i << 1].end() , seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , seg[i].bg()); } } int bsSeg(int i , int l , int r){ if(i == 1){ auto itr = lb(seg[i].bg() , seg[i].end() , l); if(itr == seg[i].end() or *itr > r) return seginf[i][0]; } if(seginf[i][0] == seginf[i][1]) return seginf[i][1] + 1; auto itr = lb(seg[(i << 1) | 1].bg() , seg[(i << 1) | 1].end() , l); if(itr != seg[i].end() and *itr <= r) return bsSeg((i << 1) | 1 , l , r); return bsSeg(i << 1 , l , r); } int cntSeg(int l , int r , int i , int val){ if(seginf[i][0] >= l and seginf[i][1] <= r) return (r - l + 1 - int(lb(seg[i].bg() , seg[i].end() , val) - seg[i].bg())); if(seginf[i][1] >= l and seginf[i][0] <= r) return (cntSeg(l , r , i << 1 , val) + cntSeg(l , r , (i << 1) | 1 , val)); return 0; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> q; for(int i = 0 ; i < n ; i++){ int d1 , d2; cin >> d1 >> d2; a.pb({d1 , d2}); } for(int i = 0 ; i < q ; i++){ int d; cin >> d; ops.pb(d); } ll o = 0; buildSeg(); for(auto el : a){ ll lsto = o; if(el[0] == el[1]) o += (1ll * el[0]); else if(el[0] < el[1]){ int inx = bsSeg(1 , el[0] , el[1] - 1); int d = 0; if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]); if(inx == 0){ if((d & 1)) o += (1ll * el[1]); else o += (1ll * el[0]); }else{ if((d & 1)) o += (1ll * el[0]); else o += (1ll * el[1]); } }else if(el[1] < el[0]){ int inx = bsSeg(1 , el[1] , el[0] - 1); int d = 0; if(inx < q) d = cntSeg(inx , q - 1 , 1 , el[1]); if((d & 1)) o += (1ll * el[1]); else o += (1ll * el[0]); } } cout << o; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:67:12: warning: unused variable 'lsto' [-Wunused-variable]
   67 |         ll lsto = o;
      |            ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...