Submission #386709

#TimeUsernameProblemLanguageResultExecution timeMemory
386709clifterStreet Lamps (APIO19_street_lamps)C++14
20 / 100
5075 ms146272 KiB
#include <iostream> #include <algorithm> #include <set> #include <vector> #define ll long long using namespace std; class event{ public: int t; int x; int y; ll value; }; bool cmpt(event a, event b){return a.t<b.t;} bool cmpx(event a, event b){if(a.x!=b.x) return a.x<b.x; else return a.t<b.t;} int last[300500],first[300500],toggle[300500]; ll ans[300500]; set<int> S; vector<event> EA; void insert(vector<ll> &tree, int i, ll val){ while(i < tree.size()) { tree[i] += val; i += (i & -i); } } ll sum(vector<ll> &tree, int i){ ll ans = 0; while (i > 0) { ans += tree[i]; i -= (i & -i); } return ans; } void cdq(int l, int r, int n){ int mid = (l+r)/2; if(l==r) return; cdq(l, mid, n); cdq(mid+1, r, n); vector<pair<int, ll>> V; vector<event> EB; event el = {l, -1, -1, 0}, er = {r+1, -1, -1, 0}; int a = lower_bound(EA.begin(), EA.end(), el, cmpt) - EA.begin(); int b = lower_bound(EA.begin(), EA.end(), er, cmpt) - EA.begin()-1; for(int i=a; i<=b; i++){ EB.push_back(EA[i]); } sort(EB.begin(), EB.end(), cmpx); vector<ll> fw1(n+2), fw2(n+2); for(int i=0; i<EB.size(); i++){ if(EB[i].t<=mid){ insert(fw1, EB[i].y, EB[i].value); insert(fw2, EB[i].y, (EB[i].value>0)?1:((EB[i].value<0)?-1:0)); } if(EB[i].t>mid) ans[EB[i].t]+=sum(fw2, EB[i].y)*(EB[i].t+1)-sum(fw1, EB[i].y); } } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, m; cin>>n>>m; string s; cin>>s; last[n+1] = n+1; first[1] = 1; for(int i=n+1; i>=2; i--) last[i-1] = (s[i-2]=='1')?last[i]:(i-1); for(int i=2; i<=n+1; i++) first[i] = (s[i-2]=='1')?first[i-1]:i; S.insert(n+1); for(int i=1; i<=n; i++) if(s[i-1]=='0') S.insert(i); for(int i=1; i<=n+1; i++){ event e[5]; e[1] = {0, i,i,1}; e[2] = {0, i,last[i]+1,-1}; e[3] = {0, i+1,i,-1}; e[4] = {0, i+1,last[i]+1, 1}; for(int j=1; j<=4; j++) EA.push_back(e[j]); } for(int i=1; i<=m; i++){ string v; cin>>v; if(v=="query"){ int x, y; cin>>x>>y; event e; e.t = i; e.x = x; e.y = y; e.value = 0; EA.push_back(e); toggle[i] = 1; } else{ int a; event e[5]; cin>>a; if(s[a-1]=='0'){ s[a-1]='1'; e[1] = {i, first[a], a+1, i+1}; e[2] = {i, first[a], last[a+1]+1, -(i+1)}; e[3] = {i, a+1, a+1, -(i+1)}; e[4] = {i, a+1, last[a+1]+1, i+1}; last[first[a]] = last[a+1]; first[last[a+1]] = first[a]; auto k = S.find(a); S.erase(k); } else{ s[a-1] = '0'; int x1, x2; x2 = *S.lower_bound(a+1); x1 = first[x2]; e[1] = {i, x1, a+1, -(i+1)}; e[2] = {i, x1, x2+1, i+1}; e[3] = {i, a+1, a+1, i+1}; e[4] = {i, a+1, x2+1, -(i+1)}; last[x1] = a; last[a+1] = x2; first[a] = x1; first[x2] = a+1; S.insert(a); } for(int j=1; j<=4; j++) EA.push_back(e[j]); } } cdq(0, m, n); for(int i=1; i<=m; i++){ if(toggle[i]==1) cout<<ans[i]<<"\n"; } }

Compilation message (stderr)

street_lamps.cpp: In function 'void insert(std::vector<long long int>&, int, long long int)':
street_lamps.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   while(i < tree.size()) {
      |         ~~^~~~~~~~~~~~~
street_lamps.cpp: In function 'void cdq(int, int, int)':
street_lamps.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0; i<EB.size(); i++){
      |                ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...