oj.uz

Submission #259470

# Submission time Handle Problem Language Result Execution time Memory
259470 2020-08-07T21:51:55 Z Goolakh Street Lamps (APIO19_street_lamps) C++17
20 / 100
 3061 ms 244440 KB 
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP _  Who? _
// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP _  You  _
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=3e5+10, maxm=1e6+10, lg=21, mod=998244353, inf=1e18;

#define git(x) (x&-x)
#define lc (v<<1)
#define rc (lc^1)
#define md ((s+t)>>1)

struct node{
	vector<ll> vec,bit; bool ok=0;
	void add(ll i,ll x){for(i++;i<SZ(bit);i+=git(i))bit[i]+=x;}
	ll get(ll i){ll ret=0;for(i++;i;i-=git(i))ret+=bit[i];return ret;}
}seg[maxn<<2];
ll n,q,l[maxn],r[maxn];
string S;
vector<ll> qq[maxn];

void rev(ll x,ll s=1,ll t=n+1,ll v=1){
	if(t-s==1){
		seg[v].ok^=1;
		return;
	}
	(x<md ? rev(x,s,md,lc):rev(x,md,t,rc));
	seg[v].ok=seg[lc].ok&seg[rc].ok;
}
ll getc(ll x,ll s=1,ll t=n+1,ll v=1){
	if(s>=x || seg[v].ok) return 0;
	if(t-s==1) return s;
	ll xx=getc(x,md,t,rc);
	if(xx!=0) return xx;
	return getc(x,s,md,lc);
}
ll getr(ll x,ll s=1,ll t=n+1,ll v=1){
	if(t<=x+1 || seg[v].ok) return n+1;
	if(t-s==1) return s;
	ll xx=getr(x,s,md,lc);
	if(xx!=n+1) return xx;
	return getr(x,md,t,rc);
}
bool geto(ll l,ll r,ll s=1,ll t=n+1,ll v=1){
	if(l>=t || r<=s) return 1;
	if(l<=s && r>=t) return seg[v].ok;
	return geto(l,r,s,md,lc) && geto(l,r,md,t,rc);
}
void bild(ll s=1,ll t=n+1,ll v=1){
	if(t-s==1){
		for(auto r:qq[s]) seg[v].vec.pb(r);
		sort(all(seg[v].vec)), seg[v].vec.resize(unique(all(seg[v].vec))-seg[v].vec.begin());
		seg[v].bit.resize(SZ(seg[v].vec)+10);
		return;
	}
	bild(s,md,lc), bild(md,t,rc);
	seg[v].vec.resize(SZ(seg[lc].vec)+SZ(seg[rc].vec));
	merge(all(seg[lc].vec),all(seg[rc].vec),seg[v].vec.begin());
	seg[v].bit.resize(SZ(seg[v].vec)+10);
}
void add(ll l,ll r,ll lx,ll rx,ll x,ll s=1,ll t=n+1,ll v=1){
	if(l>=t || r<=s) return;
	if(l<=s && r>=t){
		ll L=upper_bound(all(seg[v].vec),lx)-seg[v].vec.begin();
		ll R=upper_bound(all(seg[v].vec),rx)-seg[v].vec.begin();
		seg[v].add(L,+x);
		seg[v].add(R,-x);
		return;
	}
	add(l,r,lx,rx,x,s,md,lc);
	add(l,r,lx,rx,x,md,t,rc);
}
ll get(ll l,ll r,ll s=1,ll t=n+1,ll v=1){
	ll ret=seg[v].get(lower_bound(all(seg[v].vec),r)-seg[v].vec.begin());
	if(t-s==1) return ret;
	ret+=(l<md ? get(l,r,s,md,lc):get(l,r,md,t,rc));
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>q>>S; S='#'+S;
	for(int i=0;i<q;i++){
		string s; cin>>s>>l[i];
		if(s[0]=='q') cin>>r[i], qq[l[i]].pb(r[i]);
	}
	bild();
	for(int i=1;i<=n;i++)if(S[i]=='1') add(getc(i)+1,i+1,i,getr(i),q), rev(i);
	for(int i=0;i<q;i++){
		if(r[i]){
			ll x=get(l[i],r[i]);
			if(x!=0) x+=(geto(l[i],r[i]) ? -1:+1)*(q-i-1);
			cout<<x<<'\n';
		}
		else add(getc(l[i])+1,l[i]+1,l[i],getr(l[i]),(geto(l[i],l[i]+1) ? -1:+1)*(q-i-1)), rev(l[i]);
	}
	
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 73208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 220 ms 85340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 73336 KB Output is correct
2 Correct 43 ms 73468 KB Output is correct
3 Correct 45 ms 73592 KB Output is correct
4 Correct 45 ms 73596 KB Output is correct
5 Correct 745 ms 140132 KB Output is correct
6 Correct 1236 ms 172364 KB Output is correct
7 Correct 1806 ms 203284 KB Output is correct
8 Correct 3061 ms 244440 KB Output is correct
9 Correct 266 ms 85756 KB Output is correct
10 Correct 275 ms 86904 KB Output is correct
11 Correct 301 ms 87544 KB Output is correct
12 Correct 2749 ms 242936 KB Output is correct
13 Correct 3000 ms 244188 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 73592 KB Output is correct
2 Incorrect 47 ms 73592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 73208 KB Output isn't correct
2 Halted 0 ms 0 KB -