oj.uz

답안 #834342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
834342 2023-08-22T13:16:51 Z Antekb 가로등 (APIO19_street_lamps) C++17
40 / 100
 849 ms 180220 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define pp pop_back
#define mp make_pair
using namespace std;
using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vii = vector<pii>;
void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
	cerr<<h;
	if(sizeof...(t)){
		cerr<<", ";
	}
	debug(t...);
}
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1<<19;
vi todo[N];
int pref[N+N], suf[N+N], L[N+N], R[N+N], siz[N+N], M[N], tim[N+N];
int male[N];
int ans[N], typ[N];
vector<pair<pii, pii> > U[N];
vector<pair<int, pii> > Q[N];
void upd(int v){
	int l=v+v, r=v+v+1;
	if(pref[l]==siz[l])pref[v]=pref[r]+siz[l];
	else pref[v]=pref[l];
	if(suf[r]==siz[r])suf[v]=suf[l]+siz[r];
	else suf[v]=suf[r];
}
int tab[N+N];
void add(int v, int c){
	for(v+=N; v>0; v>>=1){
		tab[v]+=c;
	}
}
int sum(int l, int r){
	int res=0;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1)res+=tab[l++];
		if(r&1)res+=tab[--r];
	}
	return res;
}
int main(){
	int n, q;
	cin>>n>>q;
	string s;
	cin>>s;
	for(int i=0; i<n; i++){
		siz[N+i]=1;
		L[N+i]=i;
		R[N+i]=i+1;
		suf[N+i]=pref[N+i]=(s[i]-'0');
	}
	for(int i=N-1; i; i--){
		siz[i]=siz[i+i]+siz[i+i+1];
		L[i]=L[i+i];
		M[i]=R[i+i];
		if(R[i+i+1]==0)R[i]=R[i+i];
		else R[i]=R[i+i+1];
		upd(i);
	}
	for(int qq=1; qq<=q; qq++){
		cin>>s;
		if(s[0]=='q'){
			//deb(qq);
			typ[qq]=1;
			int a, b;
			cin>>a>>b;
			a--;
			b--;
			if(a==b-1){
				//deb(a, suf[N+a], tim[N+a]);
				ans[qq]=male[a]+suf[N+a]*(qq-tim[N+a]);
				continue;
			}
			//[a, b)
			int v=1;
			while(v<N){
				int m=M[v];
				if(m>=b)v=v+v;
				else if(m<=a)v=v+v+1;
				else{
					int x=m-a, y=b-m;
					//deb(v, L[v], R[v], suf[v+v], pref[v+v+1], qq-tim[v]);deb(x, y);
					if(suf[v+v]>=x && pref[v+v+1]>=y){
						ans[qq]+=qq-tim[v];
					}
					Q[v].eb(qq, mp(x, y));
					break;
				}
			}

		}
		else{
			int v;
			cin>>v;
			v--;
			if(suf[N+v]){
				male[v]+=qq-tim[N+v];
			}
			v+=N;
			tim[v]=qq;
			for(int vv=v/2; vv; vv/=2){
				U[vv].eb(mp(qq, qq-tim[vv]), mp(suf[vv+vv], pref[vv+vv+1]));
			}
			suf[v]^=1;
			pref[v]^=1;
			for(v/=2; v; v/=2){
				//deb(v, L[v], R[v], suf[v+v], pref[v+v+1], qq-tim[v]);
				tim[v]=qq;
				upd(v);
			}
		}
	}
	for(int v=1; v<N; v++){
		if(Q[v].size()){
			vector<pair<pii, pii> > UU=U[v];
			for(auto &i:UU){
				swap(i.st, i.nd);
			}
			sort(all(UU));
			reverse(all(UU));
			sort(all(Q[v]), [](pair<int,pii> a, pair<int, pii> b)
				{return a.nd>b.nd;});
			for(auto i:UU){
				//deb(i.st.st, i.st.nd, i.nd.st,i.nd.nd);
			}
			for(auto i:Q[v]){
				//deb(i.st, i.nd.st,i.nd.nd);
			}
			int wsk=0;
			for(auto i:Q[v]){
				while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){
					add(UU[wsk].st.nd, UU[wsk].nd.nd);
					wsk++;
				}
				ans[i.st]+=sum(i.nd.nd, N);
			}
			wsk=0;
			for(auto i:Q[v]){
				while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){
					add(UU[wsk].st.nd, -UU[wsk].nd.nd);
					wsk++;
				}
			}
			/*for(auto j:U[v]){
				for(auto i:Q[v]){
					if(j.st.st<=i.st && j.nd.st>=i.nd.st && j.nd.nd>=i.nd.nd){
						ans[i.st]+=j.st.nd;
					}
				}
			}*/
		}
	}
	for(int i=1; i<=q; i++){
		if(typ[i])cout<<ans[i]<<"\n";
	}
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:136:13: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  136 |    for(auto i:UU){
      |             ^
street_lamps.cpp:139:13: warning: variable 'i' set but not used [-Wunused-but-set-variable]
  139 |    for(auto i:Q[v]){
      |             ^
street_lamps.cpp:144:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){
      |           ~~~^~~~~~~~~~
street_lamps.cpp:152:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |     while(wsk<UU.size() && UU[wsk].st.st>=i.nd.st){
      |           ~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 49620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 332 ms 100760 KB Output is correct
2 Correct 286 ms 99972 KB Output is correct
3 Correct 250 ms 102176 KB Output is correct
4 Correct 471 ms 123584 KB Output is correct
5 Correct 428 ms 106820 KB Output is correct
6 Correct 465 ms 136088 KB Output is correct
7 Correct 223 ms 58728 KB Output is correct
8 Correct 225 ms 60224 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 50088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 49780 KB Output is correct
2 Correct 28 ms 49824 KB Output is correct
3 Correct 29 ms 50004 KB Output is correct
4 Correct 29 ms 50044 KB Output is correct
5 Correct 292 ms 67544 KB Output is correct
6 Correct 452 ms 104752 KB Output is correct
7 Correct 619 ms 145104 KB Output is correct
8 Correct 792 ms 180220 KB Output is correct
9 Correct 558 ms 136404 KB Output is correct
10 Correct 764 ms 152012 KB Output is correct
11 Correct 575 ms 136380 KB Output is correct
12 Correct 849 ms 151968 KB Output is correct
13 Correct 571 ms 136520 KB Output is correct
14 Correct 751 ms 151652 KB Output is correct
15 Correct 276 ms 68624 KB Output is correct
16 Correct 281 ms 70116 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 49620 KB Output isn't correct
2 Halted 0 ms 0 KB -