제출 #344822

#제출 시각아이디문제언어결과실행 시간메모리
344822alishahali1382가로등 (APIO19_street_lamps)C++14
100 / 100
3495 ms95528 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O2,unroll-loops") //#pragma GCC optimize("no-stack-protector,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<pii, int> piii; typedef pair<ll, ll> pll; #define debug(x) cerr<<#x<<'='<<(x)<<endl; #define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl; #define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl; #define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;} #define all(x) x.begin(), x.end() #define pb push_back #define kill(x) return cout<<x<<'\n', 0; const int inf=1000000010; const ll INF=10000000000000010LL; const int mod=1000000007; const int MAXN=300010, LOG=20; int n, m, k, u, v, x, y, t, a, b, ans; int QA[MAXN], QB[MAXN]; int segl[MAXN<<2], segr[MAXN<<2]; pii seg[LOG][MAXN]; int fen[LOG][MAXN]; vector<int> Q[MAXN]; string S, typ[MAXN]; set<int> st; void Build(int h, int id, int tl, int tr){ if (tr-tl==1){ segr[id]=segl[id]; for (int i:Q[tl]) seg[h][segr[id]++]={QB[i], i}; sort(seg[h]+segl[id], seg[h]+segr[id]); } else{ int mid=(tl+tr)>>1; segl[id<<1]=segl[id]; Build(h+1, id<<1, tl, mid); segl[id<<1 | 1]=segr[id<<1]; Build(h+1, id<<1 | 1, mid, tr); merge(seg[h+1]+segl[id<<1], seg[h+1]+segr[id<<1], seg[h+1]+segl[id<<1 | 1], seg[h+1]+segr[id<<1 | 1], seg[h]+segl[id]); segr[id]=segr[id<<1 | 1]; } } inline void add(int h, int pos, int val){ for (; pos<MAXN; pos+=pos&-pos) fen[h][pos]+=val; } inline int get(int h, int pos){ int res=0; for (; pos; pos-=pos&-pos) res+=fen[h][pos]; return res; } void Add(int h, int id, int tl, int tr, int l, int r, int ll, int rr, int val){ if (r<=tl || tr<=l) return ; if (l<=tl && tr<=r){ int pl=lower_bound(seg[h]+segl[id], seg[h]+segr[id], pii(ll, 0))-seg[h]; int pr=upper_bound(seg[h]+segl[id], seg[h]+segr[id], pii(rr, inf))-seg[h]; add(h, pl, +val); add(h, pr, -val); return ; } int mid=(tl+tr)>>1; Add(h+1, id<<1, tl, mid, l, r, ll, rr, val); Add(h+1, id<<1 | 1, mid, tr, l, r, ll, rr, val); } int Get(int h, int id, int tl, int tr, int i){ if (QA[i]<tl || tr<=QA[i]) return 0; int res=get(h, lower_bound(seg[h]+segl[id], seg[h]+segr[id], pii(QB[i], i))-seg[h]); if (tr-tl==1) return res; int mid=(tl+tr)>>1; return res+Get(h+1, id<<1, tl, mid, i) + Get(h+1, id<<1 | 1, mid, tr, i); } bool check(int l, int r){ return (*st.lower_bound(l))==(*st.lower_bound(r)); } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); cin>>n>>m>>S; for (int i=1; i<=m; i++){ cin>>typ[i]>>QA[i]; if (typ[i]=="query"){ cin>>QB[i]; Q[QA[i]].pb(i); } } segl[1]=1; Build(0, 1, 1, n+1); S="0"+S+"0"; for (int i=0; i<=n+1; i++) if (S[i]=='0') st.insert(i); for (int i=1; i<=m; i++){ if (typ[i]=="query"){ ans=Get(0, 1, 1, n+1, i); if (check(QA[i], QB[i])) ans+=i; cout<<ans<<"\n"; continue ; } int pos=QA[i]; if (S[pos]=='0'){ auto it=st.lower_bound(pos); int x=*--it; ++it; int y=*++it; Add(0, 1, 1, n+1, x+1, pos+1, pos+1, y, -i); S[pos]='1'; st.erase(pos); } else{ auto it=st.lower_bound(pos); int y=*it; int x=*--it; Add(0, 1, 1, n+1, x+1, pos+1, pos+1, y, +i); S[pos]='0'; st.insert(pos); } } return 0; }
#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...