제출 #69324

#제출 시각아이디문제언어결과실행 시간메모리
69324ekremBubble Sort 2 (JOI18_bubblesort2)C++98
22 / 100
232 ms104104 KiB
#include <bits/stdc++.h> #include "bubblesort2.h" #define orta ((bas + son)/2) #define sol (k+k) #define sag (k+k+1) #define st first #define nd second #define mp make_pair #define pb push_back #define N 1000005 using namespace std; typedef vector < int > vi; int n, m, q, yer[4*N], yerl[4*N], cvp[4*N], cvpl[4*N]; set < int > s[N]; void yerbu(int k, int bas, int son); void yerput(int k, int bas, int son, int l); void yerpush(int k, int bas, int son); void yerset(int k, int bas, int son, int x, int y); void yerup(int k, int bas, int son, int x, int y, int z); int yerqu(int k, int bas, int son, int x); int yersor(int k, int bas, int son, int x, int y); void cvpput(int k, int bas, int son, int l); void cvppush(int k, int bas, int son); void cvpset(int k, int bas, int son, int x, int y); void cvpup(int k, int bas, int son, int x, int y, int z); int cvpqu(int k, int bas, int son, int x); vi countScans(vi a, vi b, vi c){ vi ans; n = a.size(); m = 102; q = b.size(); for(int i = 0; i < n; i++) s[a[i]].insert(i); vi d = a; sort(d.begin(), d.end()); for(int i = 0; i < n; i++){ if(i + 1 != n and d[i + 1] == d[i]) continue; yerset(1, 1, m, d[i], i); } for(int i = 0; i < n; i++){ int son = *s[a[i]].rbegin(); int yr = yerqu(1, 1, m, a[i]); cvpset(1, 1, m, a[i], son - yr); } for(int i = 0; i < q; i++){ int yr = b[i]; int yeni = c[i]; int eski = a[b[i]]; a[yr] = yeni; if(yeni == eski){ ans.pb(cvp[1]); continue; } s[eski].erase(yr); s[yeni].insert(yr); if(eski < yeni){ yerup(1, 1, m, eski, yeni - 1, -1); cvpup(1, 1, m, eski + 1, yeni - 1, 1); if(!s[eski].empty()) cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) ); else{ yerset(1, 1, m, eski, -1); cvpset(1, 1, m, eski, 0); } if(s[yeni].size() == 1) yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1); cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) ); } if(eski > yeni){ yerup(1, 1, m, yeni, eski - 1, 1); cvpup(1, 1, m, yeni + 1, eski - 1, -1); if(!s[eski].empty()) cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) ); else{ yerset(1, 1, m, eski, -1); cvpset(1, 1, m, eski, 0); } if(s[yeni].size() == 1) yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1); cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) ); } ans.pb(cvp[1]); } return ans; } // int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // int n,q; // scanf("%d %d",&n ,&q); // vi a(n); // for(int i=0;i<n;i++) // scanf("%d",&a[i]); // vi b(q), c(q); // for(int j=0;j<q;j++){ // scanf("%d %d",&b[j], &c[j]); // } // vi cvp = countScans(a, b, c); // for(int j=0;j<int(cvp.size());j++) // printf("%d\n",cvp[j]); // } void yerbu(int k, int bas, int son){ if(bas == son) yer[k] = -1; yerbu(sol, bas, orta); yerbu(sag, orta + 1, son); } void yerput(int k, int l){ yer[k] += l; yerl[k] += l; } void yerpush(int k){ yerput(sol, yerl[k]); yerput(sag, yerl[k]); yerl[k] = 0; } void yerset(int k, int bas, int son, int x, int y){ if(bas == son){ yer[k] = y; return; } yerpush(k); if(x <= orta) yerset(sol, bas, orta, x, y); else yerset(sag, orta + 1, son, x, y); yer[k] = max(yer[sol] , yer[sag]); } void yerup(int k, int bas, int son, int x, int y, int z){ if(bas > y or son < x) return; if(bas >= x and son <= y){ yerput(k, z); return; } yerpush(k); yerup(sol, bas, orta, x, y, z); yerup(sag, orta + 1, son, x, y, z); yer[k] = max(yer[sol] , yer[sag]); } int yerqu(int k, int bas, int son, int x){ if(bas == son) return yer[k]; yerpush(k); if(x <= orta) return yerqu(sol, bas, orta, x); return yerqu(sag, orta + 1, son, x); } int yersor(int k, int bas, int son, int x, int y){ if(bas > y or son < x) return -1; if(bas >= x and son <= y) return yer[k]; return max(yersor(sol, bas, orta , x, y), yersor(sag, orta + 1, son, x, y)); } void cvpput(int k, int l){ cvp[k] += l; cvpl[k] += l; } void cvppush(int k){ cvpput(sol, cvpl[k]); cvpput(sag, cvpl[k]); cvpl[k] = 0; } void cvpset(int k, int bas, int son, int x, int y){ if(bas == son){ cvp[k] = y; return; } cvppush(k); if(x <= orta) cvpset(sol, bas, orta, x, y); else cvpset(sag, orta + 1, son, x, y); cvp[k] = max(cvp[sol] , cvp[sag]); } void cvpup(int k, int bas, int son, int x, int y, int z){ if(bas > y or son < x) return; if(bas >= x and son <= y){ cvpput(k, z); return; } cvppush(k); cvpup(sol, bas, orta, x, y, z); cvpup(sag, orta + 1, son, x, y, z); cvp[k] = max(cvp[sol] , cvp[sag]); } int cvpqu(int k, int bas, int son, int x){ if(bas == son) return cvp[k]; cvppush(k); if(x <= orta) return cvpqu(sol, bas, orta, x); return cvpqu(sag, orta + 1, son, x); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...