제출 #743933

#제출 시각아이디문제언어결과실행 시간메모리
743933ThMinh_가로등 (APIO19_street_lamps)C++14
0 / 100
288 ms38600 KiB
#include<bits/stdc++.h> #define forin(i,a,b) for(int i=a;i<=b;++i) #define fi first #define la second using namespace std; const int N = 3e5 + 10; int n, q; vector<int> bit[N], tr[N]; bool a[N]; set<pair<int, int>> st; struct query { string s; int i, a, b; }; query d[N]; void fakeup(int f, int l) { while(f <= n + 1) { bit[f].push_back(l); f += f & -f; } } void fakeget(int f, int l) { while(f) { bit[f].push_back(l); f -= f & -f; } } void up(int f, int l, int val) { while(f <= n + 1) { int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1; while(y) { tr[f][y - 1] += val; y -= y & -y; } f += f & -f; } } int get(int f, int l) { int res = 0; while(f) { int y = lower_bound(bit[f].begin(), bit[f].end(), l) - bit[f].begin() + 1; while(y <= n + 1) { res += tr[f][y - 1]; y += y & -y; } f -= f & -f; } return res; } void fakeadd(int f, int l) { fakeup(f, l + 1); st.insert({f, l}); } void add(int f, int l, int val) { up(f, l + 1, val); st.insert({f, l}); } int main () { cin.tie(0)->sync_with_stdio(0); if(fopen("Task.inp","r")) { freopen("Task.inp","r",stdin); freopen("WA.out","w",stdout); } cin>>n>>q; string s; cin>>s; s = " " + s; forin(i,1,n) a[i] = (s[i] == '1'); int f = -1; forin(i,1,n + 1) { if(f == -1 && a[i]) f = i; if(f != -1 && !a[i]) { fakeadd(f, i - 1); f = -1; } } st.insert({-1, -1}); st.insert({1e9, 1e9}); forin(j,1,q) { cin>>d[j].s; string s = d[j].s; if(s[0] == 't') { int i; cin>>i; d[j].i = i; auto i1 = st.upper_bound({i, 1e9}); auto i2 = i1--; pair<int, int> cur = *i1; pair<int, int> aft = *i2; if(cur.la + 1 < i && i < aft.fi - 1) fakeadd(i, i); else if(i == cur.la + 1 && i == aft.fi - 1) { st.erase(i1); fakeup(cur.fi, cur.la + 1); st.erase(i2); fakeup(aft.fi, aft.la + 1); fakeadd(cur.fi, aft.la); } else if(i == cur.la + 1) { st.erase(i1); fakeup(cur.fi, cur.la + 1); fakeadd(cur.fi, cur.la + 1); } else if(i == aft.fi - 1) { st.erase(i2); fakeup(aft.fi, aft.la + 1); fakeadd(aft.fi - 1, aft.la); } else if(i <= cur.la) { st.erase(i1); fakeup(cur.fi, cur.la + 1); if(cur.fi != aft.la) { if(i == cur.fi) fakeadd(cur.fi + 1, cur.la); else if(i == cur.la) fakeadd(cur.fi, cur.la - 1); else { fakeadd(cur.fi, i - 1); fakeadd(i + 1, cur.la); } } } } else { cin>>d[j].a>>d[j].b; fakeget(d[j].a, d[j].b); } } forin(i,1,n + 1) { sort(bit[i].begin(), bit[i].end()); bit[i].resize(unique(bit[i].begin(), bit[i].end()) - bit[i].begin()); tr[i].resize(bit[i].size()); } while(!st.empty()) st.erase(st.begin()); f = -1; forin(i,1,n + 1) { if(f == -1 && a[i]) f = i; if(f != -1 && !a[i]) { add(f, i - 1, q); f = -1; } } st.insert({-1, -1}); st.insert({1e9, 1e9}); forin(j,1,q) { string s = d[j].s; if(s[0] == 't') { int i = d[j].i; auto i1 = st.upper_bound({i, 1e9}); auto i2 = i1--; pair<int, int> cur = *i1; pair<int, int> aft = *i2; int val = q - j; if(cur.la + 1 < i && i < aft.fi - 1) add(i, i, val); else if(i == cur.la + 1 && i == aft.fi - 1) { st.erase(i1); up(cur.fi, cur.la + 1, -val); st.erase(i2); up(aft.fi, aft.la + 1, -val); add(cur.fi, aft.la, val); } else if(i == cur.la + 1) { st.erase(i1); up(cur.fi, cur.la + 1, -val); add(cur.fi, cur.la + 1, val); } else if(i == aft.fi - 1) { st.erase(i2); up(aft.fi, aft.la + 1, -val); add(aft.fi - 1, aft.la, val); } else if(i <= cur.la) { st.erase(i1); up(cur.fi, cur.la + 1, -val); if(cur.fi != cur.la) { if(i == cur.fi) add(cur.fi + 1, cur.la, val); else if(i == cur.la) add(cur.fi, cur.la - 1, val); else { add(cur.fi, i - 1, val); add(i + 1, cur.la, val); } } } } else { int a = d[j].a, b = d[j].b; pair<int, int> it = *--st.upper_bound({a, 1e9}); if(it.fi <= a && b <= it.la + 1) cout<<get(a, b) - (q - j)<<"\n"; else cout<<get(a, b)<<"\n"; } } }

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("Task.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("WA.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...