oj.uz

Submission #384147

# Submission time Handle Problem Language Result Execution time Memory
384147 2021-03-31T14:33:56 Z Kalashnikov Street Lamps (APIO19_street_lamps) C++17
20 / 100
 925 ms 524288 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 329196 KB Output is correct
2 Correct 195 ms 329324 KB Output is correct
3 Correct 198 ms 329196 KB Output is correct
4 Correct 199 ms 329324 KB Output is correct
5 Correct 217 ms 329196 KB Output is correct
6 Correct 200 ms 329324 KB Output is correct
7 Correct 201 ms 329324 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 335020 KB Output is correct
2 Correct 488 ms 338764 KB Output is correct
3 Correct 700 ms 340648 KB Output is correct
4 Runtime error 848 ms 524288 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 329196 KB Output is correct
2 Correct 202 ms 329324 KB Output is correct
3 Correct 208 ms 329196 KB Output is correct
4 Correct 357 ms 344088 KB Output is correct
5 Runtime error 925 ms 524288 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 329176 KB Output is correct
2 Correct 212 ms 329256 KB Output is correct
3 Correct 211 ms 329196 KB Output is correct
4 Correct 204 ms 329196 KB Output is correct
5 Runtime error 840 ms 524288 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 329196 KB Output is correct
2 Correct 195 ms 329324 KB Output is correct
3 Correct 198 ms 329196 KB Output is correct
4 Correct 199 ms 329324 KB Output is correct
5 Correct 217 ms 329196 KB Output is correct
6 Correct 200 ms 329324 KB Output is correct
7 Correct 201 ms 329324 KB Output is correct
8 Correct 452 ms 335020 KB Output is correct
9 Correct 488 ms 338764 KB Output is correct
10 Correct 700 ms 340648 KB Output is correct
11 Runtime error 848 ms 524288 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -