oj.uz

Submission #406984

# Submission time Handle Problem Language Result Execution time Memory
406984 2021-05-18T09:37:21 Z amunduzbaev Street Lamps (APIO19_street_lamps) C++14
20 / 100
 258 ms 41636 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>

const int N = 105;
const int M = 3e5+5;
const int mod = 1e9+7;

int n, m, k, a[M];
int rr[N][N];
vector<int> in[M], qq[M];
int tree[4*M], p[4*M];

void push(int x, int lx, int rx){
	if(lx == rx || !p[x]) return;
	int m = (lx + rx)>>1;
	tree[x<<1] += (m - lx + 1) * p[x], p[x<<1] += p[x];
	tree[x<<1|1] += (rx - m) * p[x], p[x<<1|1] += p[x];
	p[x] = 0;
}

void sett(int l, int r, int v, int lx = 0, int rx = m, int x = 1){
	push(x, lx, rx);
	if(lx > r || rx < l) return;
	if(lx >= l && rx <= r){
		tree[x] += (rx - lx + 1) * v;
		p[x] += v; return;
	} int m = (lx + rx)>>1;
	sett(l, r, v, lx, m, x<<1), sett(l, r, v, m+1, rx, x<<1|1);
}

int find(int l, int r, int lx = 0, int rx = m, int x = 1){
	push(x, lx, rx);
	if(lx > r || rx < l) return 0;
	if(lx >= l && rx <= r) return tree[x];
	int m = (lx + rx)>>1;
	return find(l, r, lx, m, x<<1) + find(l, r, m+1, rx, x<<1|1);
}

/*

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

*/

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin>>n>>m;
	string s; cin>>s;
	
	for(int i=0;i<n;i++) a[i] = s[i] - '0';
	if(n <= 100 && m <= 100) {
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				int l = j;
				while(l < n && a[l]) rr[j][l]++, l++;
			} cin>>s;
			if(s == "query"){
				int a, b; cin>>a>>b, a--, b-=2;
				cout<<rr[a][b]<<"\n";
			} else {
				int in; cin>>in, in--;
				a[in] ^= 1;
			}
		} return 0; 
	} 
	
	vector<pair<int, int>> tt;
	bool ok = 1;
	
	for(int i=0;i<m;i++){
		string s; cin>>s;
		int a, b, in;
		if(s == "query") cin>>a>>b, --b, tt.pb({a-1, b-1}), ok &= (a == b);
		else cin>>in, tt.pb({-1, --in});
	} 

/*

5 7
11011
query 1 2
query 1 2
query 5 6
query 3 4
toggle 3
query 3 4
query 5 6

*/
	
	if(ok){
		vector<int> rr(m);
		for(int i=0;i<n;i++) if(a[i]) in[i].pb(0);
		for(int i=0;i<sz(tt);i++){
			if(tt[i].ff == -1) in[tt[i].ss].pb(i+1);
			else qq[tt[i].ff].pb(i);
		}
		for(int i=0;i<n;i++){
			if(sz(in[i]) & 1) in[i].pb(m);
			for(int j=0;j<sz(in[i]);j+=2) sett(in[i][j], in[i][j+1], 1);
			for(auto x : qq[i]) rr[x] = find(0, x);
			for(int j=0;j<sz(in[i]);j+=2) sett(in[i][j], in[i][j+1], -1);
		}
		for(int i=0;i<m;i++){
			if(~tt[i].ff) cout<<rr[i]<<"\n";
		} cout<<"\n"; 
		return 0;
	} else {
		
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 9 ms 14376 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 11 ms 14348 KB Output is correct
7 Correct 10 ms 14460 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 9 ms 14412 KB Output is correct
3 Correct 9 ms 14376 KB Output is correct
4 Correct 9 ms 14460 KB Output is correct
5 Correct 10 ms 14412 KB Output is correct
6 Correct 11 ms 14348 KB Output is correct
7 Correct 10 ms 14460 KB Output is correct
8 Incorrect 258 ms 41636 KB Output isn't correct
9 Halted 0 ms 0 KB -