Submission #268276

#TimeUsernameProblemLanguageResultExecution timeMemory
268276evpipisStreet Lamps (APIO19_street_lamps)C++11
20 / 100
5054 ms121280 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back typedef pair<int, int> ii; const int len = 3e5+5; set<ii> mys; int light[len]; // n_len struct seg_tree{ int mx; vector<pair<int, ii> > vec; seg_tree(int m = 0){ mx = m; } void upd(int y, int sum, int num){ vec.pb(mp(y, mp(sum, num))); } ii ask(int y_){ int sum_ = 0, num_ = 0; for (int j = 0; j < vec.size(); j++){ int y = vec[j].fi, sum = vec[j].se.fi, num = vec[j].se.se; if (y >= y_) sum_ += sum, num_ += num; } return mp(sum_, num_); } }; struct bit{ seg_tree tree[len]; int mx; bit(int r = 0, int c = 0){ mx = r; for (int i = 1; i <= r; i++) tree[i] = seg_tree(c); } void upd(int x, int y, int sum, int num){ while (x <= mx) tree[x].upd(y, sum, num), x += x&(-x); } int ask(int x, int y, int tim){ int sum = 0, num = 0; while (x > 0){ sum += tree[x].ask(y).fi; num += tree[x].ask(y).se; x -= x&(-x); } return sum + num*tim; } }; bit data; ii rig(int i){ auto it = mys.lower_bound(mp(i, 0)); if (it == mys.end()) return mp(-1, -1); return *it; } ii lef(int i){ auto it = mys.lower_bound(mp(i+1, 0)); if (it == mys.begin()) return mp(-1, -1); return *(--it); } void print(){ printf("current intervals:"); for (auto it: mys) printf(" (%d, %d)", it.fi, it.se); printf("\n"); } void toggle(int i, int t = 0){ light[i] ^= 1; if (light[i] == 1){ ii cur = mp(i, i), l = lef(i-1), r = rig(i+1); if (l.se+1 == cur.fi){ // remove l and update data and extend cur mys.erase(l); data.upd(l.fi, l.se, +t, -1); cur.fi = l.fi; } if (cur.se == r.fi-1){ // remove r and update data and extend cur mys.erase(r); data.upd(r.fi, r.se, +t, -1); cur.se = r.se; } // insert cur and update data mys.insert(cur); data.upd(cur.fi, cur.se, -t, +1); } else{ ii cur = lef(i), l = mp(cur.fi, i-1), r = mp(i+1, cur.se); // remove cur and update data mys.erase(cur); data.upd(cur.fi, cur.se, +t, -1); if (l.fi <= l.se){ // insert l and update data mys.insert(l); data.upd(l.fi, l.se, -t, +1); } if (r.fi <= r.se){ // insert r and update data mys.insert(r); data.upd(r.fi, r.se, -t, +1); } } //print(); } int main(){ int n, q; scanf("%d %d ", &n, &q); data = bit(n, n); for (int i = 1; i <= n; i++){ char temp; scanf("%c", &temp); if (temp == '1') toggle(i); } for (int i = 1; i <= q; i++){ char str[15]; scanf("%s", str); if (str[0] == 'q'){ int a, b; scanf("%d %d", &a, &b); b--; printf("%d\n", data.ask(a, b, i)); //printf("asked for interval (%d, %d)\n", a, b); } else{ int pos; scanf("%d", &pos); toggle(pos, i); } //printf("%d) ", i); //print(); } return 0; }

Compilation message (stderr)

street_lamps.cpp: In member function 'ii seg_tree::ask(int)':
street_lamps.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for (int j = 0; j < vec.size(); j++){
      |                         ~~^~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:132:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  132 |     scanf("%d %d ", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:138:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |         scanf("%c", &temp);
      |         ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  145 |         scanf("%s", str);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:148:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  156 |             scanf("%d", &pos);
      |             ~~~~~^~~~~~~~~~~~
#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...