Submission #249093

#TimeUsernameProblemLanguageResultExecution timeMemory
249093crossing0verStreet Lamps (APIO19_street_lamps)C++17
40 / 100
5068 ms43660 KiB
#include<bits/stdc++.h> #define pb push_back #define ll long long using namespace std; const int N = 3e5+5; int n,q; string S; bool s[N]; void Small() { string type; vector<int> Q; Q.pb(-1); for (int rep = 0,a,b,x; rep < q; rep++) { cin >> type; if (type[0] == 't') { cin >> x; x--; Q.pb(x); } else { cin >> a >> b; a--; b-=2; int ans = 0; for (int i : Q) { if (i != -1 ) s[i] = (!s[i]); bool flag = 1; for (int i = a; i <= b; i++) if (s[i] == 0) flag = 0; if (flag) ans++; } for (int i : Q) if (i != -1) s[i] = (!s[i]); cout << ans <<'\n'; Q.pb(-1); } } exit(0); } struct { bool type; int a,b; }quest[N]; void CaseAdj() { vector<int> last(n+1,-1),ans(n+1); for (int i = 0; i < q;i++) { if (quest[i].type == 0) { int x = quest[i].a; if (s[x] == 1) { ans[x] += i -last[x]; } else { last[x] = i; // or i+1 } s[x] = (!s[x]); } else { int x = quest[i].a; cout << ans[x] + (s[x] ? i - last[x] : 0) <<'\n'; } } exit(0); } set<int> L[N]; int vis[N],bit[N]; map<pair<int,int>,int> last; void add(int pos) { for (pos++;pos < N; pos += pos & -pos) bit[pos]++; } int get(int pos) { int s = 0; for (++pos;pos;pos-=pos&-pos) s+= bit[pos]; return s; } int get(int l,int r) { return get(r) - get(l-1); } void Case3() { for (int i = 0; i < n; i++) if (s[i]) add(i); for (int rep = 0;rep < q ; rep ++) { if (quest[rep].type == 0) { int x = quest[rep].a; assert(s[x] == 0); s[x] = 1; add[x]; int R; for (int i = x; i < n && s[i] == 1; i++) { R = i; } for (int i = x; i >= 0 && s[i] == 1; i--) { for (int b : L[i]) { if (b >= x && b <= R) { last[{i,b}] = rep; } } } } else { int x = quest[rep].a, y = quest[rep].b; if ((get(x,y)) == y-x+1) cout << rep - last[{x,y}] <<'\n'; else cout << 0 <<'\n'; } } } main() { ios::sync_with_stdio(0); cin >> n >> q >> S; for (int i = 0; i < S.size(); i++) s[i] = (S[i] == '1'); if (n <= 100 && q <= 100) Small(); string tp; bool flag = 1,fl = 1; for (int i = 0,x; i < q; i++) { cin >> tp; if (tp[0] == 't') { quest[i].type = 0; cin >> x; x--; if (vis[x]) fl = 0; vis[x] = 1; if (s[x] == 1) fl = 0; quest[i].a = x; } else { quest[i].type = 1; cin >> quest[i].a >> quest[i].b; quest[i].a--; quest[i].b-=2; last[{quest[i].a,quest[i].b}] = -1; if (quest[i].a != quest[i].b) flag = 0; L[quest[i].a].insert(quest[i].b); } } if (flag == 1) CaseAdj(); if (fl) Case3(); while(true){ } }

Compilation message (stderr)

street_lamps.cpp: In function 'void Case3()':
street_lamps.cpp:91:9: warning: pointer to a function used in arithmetic [-Wpointer-arith]
    add[x];
         ^
street_lamps.cpp:91:9: warning: value computed is not used [-Wunused-value]
    add[x];
    ~~~~~^
street_lamps.cpp:91:9: warning: statement has no effect [-Wunused-value]
street_lamps.cpp: At global scope:
street_lamps.cpp:117:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:120:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < S.size(); i++)
                  ~~^~~~~~~~~~
street_lamps.cpp: In function 'void Case3()':
street_lamps.cpp:98:17: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (b >= x && b <= R) {
          ~~~~~~~^~~~~~~~~
#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...