oj.uz

Submission #136602

# Submission time Handle Problem Language Result Execution time Memory
136602 2019-07-25T17:58:46 Z liwi Street Lamps (APIO19_street_lamps) C++11
60 / 100
 5000 ms 331460 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 300005
#define MAXS 20000000

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int cnt;

struct node{
//	int l,r;
	int lft,rgt;
//	ll lazy0,lazy1;
	int sum;
	short cnt; //lazy0 for sum, lazy1 for cnt
	node(){
		lft = rgt = sum = cnt = 0;
	}
//	node *lft,*rgt;
//
//	node(int l, int r){
//		this->l = l;
//		this->r = r;
//		this->lazy0 = this->lazy1 = this->sum = this->cnt = 0;
//		lft = rgt = 0;
//	}
};

int len,num_q,arr[MAXN],rt[MAXN];
node seg[MAXS];
set<int> zeros;
//
//inline void build_needed(int rt){
//	if(!seg[rt].lft){
//		seg[rt].lft = ++cnt;
//		seg[cnt] = {0,0,0,0};
//	}
//	if(!seg[rt].rgt){
//		seg[rt].rgt = ++cnt;
//		seg[cnt] = {0,0,0,0};
//	}
//}

//inline void push_down(int rt){
//	build_needed(rt);
//	seg[seg[rt].lft].lazy0+=seg[rt].lazy0, seg[seg[rt].rgt].lazy0+=seg[rt].lazy0;
//	seg[seg[rt].lft].sum+=seg[rt].lazy0, seg[seg[rt].rgt].sum+=seg[rt].lazy0;
//
//	seg[seg[rt].lft].lazy1+=seg[rt].lazy1, seg[seg[rt].rgt].lazy1+=seg[rt].lazy1;
//	seg[seg[rt].lft].cnt+=seg[rt].lazy1, seg[seg[rt].rgt].cnt+=seg[rt].lazy1;
//
//	seg[rt].lazy0 = seg[rt].lazy1 = 0;
//}

void update(int sl, int sr, int pos, int rt, int sumv, int cntv){
	if(sl == sr){
		seg[rt].sum+=sumv;
		seg[rt].cnt+=cntv;
		return;
	}
//	if(seg[rt].lazy0 || seg[rt].lazy1) push_down(rt);
//	build_needed(rt);
	int mid = (sl+sr)>>1;
	if(pos <= mid){
		if(!seg[rt].lft){
			seg[rt].lft = ++cnt;
			seg[cnt] = node();
		}
		update(sl,mid,pos,seg[rt].lft,sumv,cntv);
	}else{
		if(!seg[rt].rgt){
			seg[rt].rgt = ++cnt;
			seg[cnt] = node();
		}
		update(mid+1,sr,pos,seg[rt].rgt,sumv,cntv);
	}
	seg[rt].sum = seg[seg[rt].lft].sum+seg[seg[rt].rgt].sum;
	seg[rt].cnt = seg[seg[rt].lft].cnt+seg[seg[rt].rgt].cnt;
}

pll query(int sl, int sr, int pos, int rt){
	if(sl == sr){
		return mp(seg[rt].sum,seg[rt].cnt);
//		if(s == 0) return seg[rt].sum;
//		return seg[rt].cnt;
	}
//	if(seg[rt].lazy0 || seg[rt].lazy1) push_down(rt);
//	build_needed(rt);
	int mid = (sl+sr)>>1;
	if(pos <= mid){
		if(!seg[rt].lft) return mp(0,0);
		return query(sl,mid,pos,seg[rt].lft);
	}
	if(!seg[rt].rgt) return mp(seg[seg[rt].lft].sum,seg[seg[rt].lft].cnt);
	pll t = query(mid+1,sr,pos,seg[rt].rgt);
	t.first+=seg[seg[rt].lft].sum;
	t.second+=seg[seg[rt].lft].cnt;
	return t;
}

inline void bupdate(int xl, int xr, int l, int r, int sv, int cv){
//	for(int i=xl; i<=xr; i++)
//		bit[i].update(l,r,bit[i].rt,v);
	for(int i=xl; i<=len+1; i+=i&-i){
		if(!rt[i]){
			rt[i] = ++cnt;
			seg[cnt] = node();
		}
		update(1,len+1,l,rt[i],sv,cv);
		if(r+1 <= len+1)
			update(1,len+1,r+1,rt[i],-sv,-cv);
	}
//		bit[i].update(l,r,bit[i].rt,v,s);
//	if(r < len+1){
		for(int i=xr+1; i<=len+1; i+=i&-i){
			if(!rt[i]){
				rt[i] = ++cnt;
				seg[cnt] = node();
			}
			update(1,len+1,l,rt[i],-sv,-cv);
			if(r+1 <= len+1)
				update(1,len+1,r+1,rt[i],sv,cv);
//		update(1,len+1,l,r,rt[i],-v,s);
		}
//	}
//		bit[i].update(l,r,bit[i].rt,-v,s);
}

inline pll bquery(int a, int b){
	pll res = mp(0,0); //sum,cnt
//	res = bit[a].query(b,bit[a].rt);
	for(int i=a; i>0; i-=i&-i){
		if(!rt[i]) continue;
		pll t = query(1,len+1,b,rt[i]);
		res.first+=t.first;
		res.second+=t.second;
	}
//		res+=bit[i].query(b,bit[i].rt,s);
	return res;
}

//inline void cupdate(int xl, int xr, int l, int r, ll v){
////	for(int i=xl; i<=xr; i++)
////		cnt[i].update(l,r,cnt[i].rt,v);
//	for(int i=xl; i<=len+1; i+=i&-i)
//		cnt[i].update(l,r,cnt[i].rt,v);
//	for(int i=xr+1; i<=len+1; i+=i&-i)
//		cnt[i].update(l,r,cnt[i].rt,-v);
//}
//
//inline ll cquery(int a, int b){
//	ll res = 0;
////	res = cnt[a].query(b,cnt[a].rt);
//	for(int i=a; i>0; i-=i&-i)
//		res+=cnt[i].query(b,cnt[i].rt);
//	return res;
//}

int main(){
//	freopen("28","r",stdin);
//	fastio; cin>>len>>num_q;
	scanf("%d %d",&len,&num_q);
	for(int i=1; i<=len; i++){
		char c; scanf(" %c",&c); // cin>>c;
		arr[i] = c-'0';
	}
//	for(int i=1; i<=len+1; i++){
//		rt[i] = ++cnt;
//		seg[cnt] = {0,0,0,0};
////		bit[i].rt = new node(1,len+1);
////		cnt[i].rt = new node(1,len+1,0,0);
////		bit[i].build(1,len+1,1);
////		cnt[i].build(1,len+1,1);
//	}
	zeros.insert(0); zeros.insert(len+1);
//	cupdate(1,len+1,1,len+1,1);
	bupdate(1,len+1,1,len+1,0,1);
	int lst = 0;
	for(int a=1; a<=len; a++){
		if(arr[a] == 0){
			zeros.insert(a);
			int l = lst, r = len+1;
//			update(bit,l+1,a,a+1,r-1,i);
//			cupdate(l+1,a,a+1,r,-1);
			bupdate(l+1,a,a+1,r,0,-1);
			lst = a;
//			printf("R1: %d   R2: %d    C1: %d    C2: %d    V: %d\n",l+1,a,a+1,r,-1);
		}
	}
	for(int i=1; i<=num_q; i++){
		char op[10]; int a; scanf(" %s %d",op,&a);
//		string op; int a; cin>>op>>a;
		if(op[0] == 't'){
//			int l; // = *(--zeros.lower_bound(a));
			auto rit = zeros.upper_bound(a);
			if(arr[a] == 0){
				int r = *rit;
				int l = *(----rit);
				bupdate(l+1,a,a+1,r,-i,1);
//				bupdate(l+1,a,a+1,r,1,1);
				zeros.erase(a);
				//(previous value)+(t-i)
				//(previous value)+t-i
			}else{
				int r = *rit;
				int l = *(--rit);
				bupdate(l+1,a,a+1,r,i,-1);
//				bupdate(l+1,a,a+1,r,-1,1);
				zeros.insert(a);
				//(previous value)-(t-i)
				//(previous value)-t+i
			}
			arr[a] = !arr[a];
		}else{
			int b; scanf(" %d",&b); //cin>>b;
			pll t = bquery(a,b);
			ll f = t.second*i;
			ll s = t.first;
//			if(f+s < 0) assert(false);
//			cout<<f+s<<endl;
			printf("%lld\n",f+s);
		}
	}
//	cout<<"lol"<<endl;
}
/*
5 1
11111
query 1 2
ans=1

5 4
00001
toggle 3
toggle 2
toggle 4
query 2 6
ans=1
 */

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:204:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&len,&num_q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:206:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char c; scanf(" %c",&c); // cin>>c;
           ~~~~~^~~~~~~~~~
street_lamps.cpp:233:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char op[10]; int a; scanf(" %s %d",op,&a);
                       ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:257:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int b; scanf(" %d",&b); //cin>>b;
           ~~~~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 313568 KB Output is correct
2 Correct 281 ms 313464 KB Output is correct
3 Correct 291 ms 313420 KB Output is correct
4 Correct 290 ms 313592 KB Output is correct
5 Correct 297 ms 313436 KB Output is correct
6 Correct 285 ms 313468 KB Output is correct
7 Correct 289 ms 313456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 315316 KB Output is correct
2 Correct 635 ms 315288 KB Output is correct
3 Correct 1039 ms 315432 KB Output is correct
4 Correct 3127 ms 324472 KB Output is correct
5 Correct 2750 ms 323452 KB Output is correct
6 Correct 3373 ms 324436 KB Output is correct
7 Correct 2166 ms 331460 KB Output is correct
8 Correct 465 ms 317560 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 313664 KB Output is correct
2 Correct 286 ms 313628 KB Output is correct
3 Correct 285 ms 313464 KB Output is correct
4 Correct 284 ms 313508 KB Output is correct
5 Execution timed out 5053 ms 330540 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 313440 KB Output is correct
2 Correct 285 ms 313596 KB Output is correct
3 Correct 286 ms 313464 KB Output is correct
4 Correct 286 ms 313536 KB Output is correct
5 Correct 1020 ms 324052 KB Output is correct
6 Correct 1978 ms 323952 KB Output is correct
7 Correct 2999 ms 323960 KB Output is correct
8 Correct 4348 ms 323576 KB Output is correct
9 Correct 700 ms 314200 KB Output is correct
10 Correct 619 ms 314008 KB Output is correct
11 Correct 699 ms 314504 KB Output is correct
12 Correct 618 ms 314108 KB Output is correct
13 Correct 695 ms 314232 KB Output is correct
14 Correct 616 ms 314104 KB Output is correct
15 Correct 1447 ms 331324 KB Output is correct
16 Correct 464 ms 317276 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 313568 KB Output is correct
2 Correct 281 ms 313464 KB Output is correct
3 Correct 291 ms 313420 KB Output is correct
4 Correct 290 ms 313592 KB Output is correct
5 Correct 297 ms 313436 KB Output is correct
6 Correct 285 ms 313468 KB Output is correct
7 Correct 289 ms 313456 KB Output is correct
8 Correct 548 ms 315316 KB Output is correct
9 Correct 635 ms 315288 KB Output is correct
10 Correct 1039 ms 315432 KB Output is correct
11 Correct 3127 ms 324472 KB Output is correct
12 Correct 2750 ms 323452 KB Output is correct
13 Correct 3373 ms 324436 KB Output is correct
14 Correct 2166 ms 331460 KB Output is correct
15 Correct 465 ms 317560 KB Output is correct
16 Correct 294 ms 313664 KB Output is correct
17 Correct 286 ms 313628 KB Output is correct
18 Correct 285 ms 313464 KB Output is correct
19 Correct 284 ms 313508 KB Output is correct
20 Execution timed out 5053 ms 330540 KB Time limit exceeded
21 Halted 0 ms 0 KB -