Submission #384147

#	Time	Username	Problem	Language	Result	Execution time	Memory
384147		Kalashnikov	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	925 ms	524288 KiB

street_lamps

#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 3e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

int a[N];
int f[N];
int n , q;

int getS(int x) {
	int res = 0;
	while(x > 0) {
		res += f[x];
		x &= x+1;
		x --;
	}
	return res;
}

void upd(int pos , int op = 1) {
	for(; pos < N; pos |= pos+1) {
		f[pos] += op;
	}
}

int getl(int i) {
	int res = i;
	int l = 1 , r = i-1;
	while(l <= r) {
		int md = l+r >> 1;
		if(getS(i-1) - getS(md-1) == i-md) {
			res = md;
			r = md-1;
		}
		else {
			l = md+1;
		}
	}
	return res;
}

int getr(int i) {
	int res = i;
	int l = i+1 , r = n+1;
	while(l <= r) {
		int md = l+r >> 1;
		if(getS(md-1) - getS(i-1) == md-i) {
			res = md;
			l = md+1;
		}
		else {
			r = md-1;
		}
	}
	return res;
}

struct DO2D{
	int l , r , d1;
	vector<array<int,3>> laz;
}t[20*N];
int sz2D = 1 , sz1D = 0; 
struct DO1D{
	int l , r;
	int val = 0 , op = 0;
}t1[20*N];

void push1(int u) {
	if(t1[u].op != 0) {
		int l = t1[u].l , r = t1[u].r;
		t1[l].val += t1[u].op;
		t1[r].val += t1[u].op;
		t1[l].op += t1[u].op;
		t1[r].op += t1[u].op;
		t1[u].op = 0;
	}
}

void UPD1(int l, int r , int op , int u , int ul = 1, int ur = n+1) {
	if(t1[u].l == 0) t1[u].l = ++sz1D;
	if(t1[u].r == 0) t1[u].r = ++sz1D;
	
	if(l <= ul && ur <= r) {
		t1[u].val += op;
		t1[u].op += op;
		///cout <<"FLOW "<< t1[u].val << '\n';
		return;
	}
	if(r < ul || ur < l) return;
	
	push1(u);
	int um = ul+ur >> 1;
	UPD1(l , r , op , t1[u].l , ul , um);
	UPD1(l , r , op , t1[u].r , um+1 , ur);
}

void push(int u) {
	int l = t[u].l , r = t[u].r;
	if(t[l].d1 == 0) t[l].d1 = ++sz1D;
	if(t[r].d1 == 0) t[r].d1 = ++sz1D;
	for(auto to: t[u].laz) {
		UPD1(to[0] , to[1] , to[2] , t[l].d1);
		UPD1(to[0] , to[1] , to[2] , t[r].d1);
		t[l].laz.push_back(to);
		t[r].laz.push_back(to);
	}
	t[u].laz.clear();
}

void UPD(int x1 , int x2 , int y1 , int y2 , int op , int u = 1, int ul = 1, int ur = n+1) {
	if(t[u].l == 0) t[u].l = ++sz2D;
	if(t[u].r == 0) t[u].r = ++sz2D;
	if(x1 <= ul && ur <= x2) {
		if(t[u].d1 == 0) t[u].d1 = ++sz1D;
		UPD1(y1 , y2 , op , t[u].d1);
		t[u].laz.push_back({y1 , y2 , op});
		return;
	}
	if(ur < x1 || x2 < ul) return;
	
	push(u);
	int um = ul+ur >> 1;
	UPD(x1 , x2 , y1 , y2 , op, t[u].l , ul , um);
	UPD(x1 , x2 , y1 , y2 , op , t[u].r , um+1 , ur);
}

int get1(int pos , int u , int ul = 1, int ur = n+1) {
	if(t1[u].l == 0) t1[u].l = ++sz1D;
	if(t1[u].r == 0) t1[u].r = ++sz1D;
	
	if(ur == ul) {
		return t1[u].val;
	}
	
	push1(u);
	int um = ul+ur >> 1;
	if(pos <= um) {
		return get1(pos , t1[u].l , ul , um);
	}
	else {
		return get1(pos , t1[u].r , um+1 , ur);
	}
}

int get(int x , int y , int u = 1, int ul = 1, int ur = n+1) {
	if(t[u].l == 0) t[u].l = ++sz2D;
	if(t[u].r == 0) t[u].r = ++sz2D;
	
	if(ur == ul) {
		if(t[u].d1 == 0) t[u].d1 = ++sz1D;
		return get1(y , t[u].d1);
	}
	
	push(u);
	int um = ul+ur >> 1;
	if(x <= um) {
		return get(x , y , t[u].l , ul , um);
	}
	else {
		return get(x , y , t[u].r , um+1 , ur);
	}
}

void solve() {
	cin >> n >> q;
	for(int i = 1; i <= n; i ++) {
		char c;cin>>c;
		if(c-48) {
			int op;
			if(a[i] == 1) {
				upd(i , -1);
				op = 1;
			}
			else {
				upd(i , 1);
				op = -1;
			}
			a[i] = 1-a[i];
			int l = getl(i);
			int r = getr(i+1);
			UPD(l , i , i+1 , r , op);
		}
	}
	int curtime = 1;
	while(q --) {
		curtime ++;
		string type;
		cin >> type;
		if(type == "query") {
			int a , b;
			cin >> a >> b;
			int g = get(a , b);
			// cout << g << '\n';
			if(g < 0) g += curtime;
			cout << g << '\n';
		}
		else {
			int i , op;
			cin >> i;
			if(a[i] == 1) {
				upd(i , -1);
				op = curtime;
			}
			else {
				upd(i , 1);
				op = -curtime;
			}
			a[i] = 1-a[i];
			int l = getl(i);
			int r = getr(i+1);
		//	cout << "TOG " << l << ' ' << i << ' ' << i+1 << ' ' << r  << "  " << op<< '\n';
			UPD(l , i , i+1 , r , op);
		}
	}
}
/*
10 20
1111010011
toggle 3
toggle 1
toggle 5
toggle 5
toggle 7
query 7 10
query 6 8
query 6 8
toggle 7
toggle 4
toggle 4
toggle 3
toggle 8
toggle 8
toggle 3
query 4 6
*/
main() {
   ios;
    int tt = 1;
    //cin >> tt;
    while(tt --) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int getl(int)':
street_lamps.cpp:39:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int md = l+r >> 1;
      |            ~^~
street_lamps.cpp: In function 'int getr(int)':
street_lamps.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |   int md = l+r >> 1;
      |            ~^~
street_lamps.cpp: In function 'void UPD1(int, int, int, int, int, int)':
street_lamps.cpp:101:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |  int um = ul+ur >> 1;
      |           ~~^~~
street_lamps.cpp: In function 'void UPD(int, int, int, int, int, int, int, int)':
street_lamps.cpp:131:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |  int um = ul+ur >> 1;
      |           ~~^~~
street_lamps.cpp: In function 'int get1(int, int, int, int)':
street_lamps.cpp:145:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |  int um = ul+ur >> 1;
      |           ~~^~~
street_lamps.cpp: In function 'int get(int, int, int, int, int)':
street_lamps.cpp:164:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  164 |  int um = ul+ur >> 1;
      |           ~~^~~
street_lamps.cpp: At global scope:
street_lamps.cpp:245:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  245 | main() {
      |      ^

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20