oj.uz

Submission #292110

# Submission time Handle Problem Language Result Execution time Memory
292110 2020-09-06T11:14:33 Z kajebiii Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1515 ms 174568 KB 
// Comment
//

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;

using ti = tuple<int, int, int>;
using qi = tuple<int, int, int, int>;

const int MAX_N = 3e5 + 100;

struct IDX {
	int P; vector<int> val;
	IDX(int N) {
		for(P=1; P<N; P<<=1);
		val = vector<int>(2*P, 0);
	}
	void add(int v, int k) {
		val[v+=P] += k;
		while(v>>=1) val[v] = val[v*2] + val[v*2+1];
	}
	int getSum(int a, int b) {
		int res = 0;
		for(a+=P, b+=P; a<=b; a>>=1, b>>=1) {
			if(a%2==1) res += val[a++];
			if(b%2==0) res += val[b--];
		}
		return res;
	}
};

int N, Q;
int Nr[MAX_N];
set<ti> Lines;
vector<ti> Qs;
int Ans[MAX_N];

void addDel(vector<qi> &dels, ti del, int q) {
	int x, y, t; tie(x, y, t) = del;
	dels.push_back(qi(x, y, t, q));
}

vector<qi> Dels[MAX_N * 4];
IDX idx = IDX(1);
void dc(int ql, int qr, int ix) {
	int qm = (ql + qr) >> 1;

	vector<qi> &dels = Dels[ix];
	if(ql != qr) {
		dc(ql, qm, ix * 2);
		for(qi tt: Dels[ix*2  ]) Dels[ix].push_back(tt);
		
		sort(ALL(dels));
		// merge sort ?
		
		vector<ti> queries;
		for(int q=qm+1; q<=qr; q++) {
			if(get<0>(Qs[q]) == 1) {
				int a, b; tie(ignore, a, b) = Qs[q];
				queries.emplace_back(a, b, q);
			}
		}
		sort(ALL(queries));

		int delsIx = 0;
		for(ti query: queries) {
			int a, b, q; tie(a, b, q) = query;
			while(delsIx < SZ(dels) && get<0>(dels[delsIx]) <= a) {
				int x, y, ts, te; tie(x, y, ts, te) = dels[delsIx++];
				if(te >= ql) idx.add(y, te - max(ts, ql) + 1);
			}

			int now = idx.getSum(b, N);
			Ans[q] += now;
		}
		for(int i=0; i<delsIx; i++) {
			int x, y, ts, te; tie(x, y, ts, te) = dels[i];
			if(te >= ql) idx.add(y, -(te - max(ts, ql) + 1));
		}
		for(ti query: queries) {
			int a, b, q; tie(a, b, q) = query;
			if(SZ(Lines) == 0) continue;
			auto it = Lines.lower_bound(ti(a+1, -INF, -INF));
			it--;
			int x, y, t; tie(x, y, t) = *it;
			if(x <= a && b <= y) {
				Ans[q] += qm - max(ql, t) + 1;
			}
		}

		dc(qm+1, qr, ix*2+1);
		for(qi tt: Dels[ix*2+1]) Dels[ix].push_back(tt);
	}else{
		int q = ql;
		if(get<0>(Qs[q]) == 0) {
			int ix = get<1>(Qs[q]);
			if(Nr[ix] == 0) {
				int lv = Nr[ix-1], rv = Nr[ix+1];
				int l = ix, r = ix;
				auto it = Lines.begin();
				if(lv) {
					it = Lines.lower_bound(ti(ix, -INF, -INF));
					it--;
					l = get<0>(*it);
					Lines.erase(it);
					addDel(dels, *it, q);
				}
				if(rv) {
					it = Lines.lower_bound(ti(ix, -INF, -INF));
					r = get<1>(*it);
					Lines.erase(it);
					addDel(dels, *it, q);
				}
				Lines.emplace(ti(l, r, q+1));
			}else{
				auto it = Lines.lower_bound(ti(ix+1, -INF, -INF));
				it--;
				int l, r; tie(l, r, ignore) = *it;
				Lines.erase(it);
				addDel(dels, *it, q);

				if(l <= ix-1) Lines.emplace(ti(l, ix-1, q+1));
				if(r >= ix+1) Lines.emplace(ti(ix+1, r, q+1));
			}
			Nr[ix] = 1 - Nr[ix];
		}else{
			int a, b; tie(ignore, a, b) = Qs[q];
			if(SZ(Lines) == 0) return;
			auto it = Lines.lower_bound(ti(a+1, -INF, -INF));
			it--;
			int x, y, t; tie(x, y, t) = *it;
			if(x <= a && b <= y) {
				Ans[q] += 1;
			}
		}
	}
}
int main() {
	cin >> N >> Q;
	for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
	for(int i=1; i<=N; i++) {
		if(Nr[i] == 0) continue;
		int st = i, en = i;
		while(en+1 <= N && Nr[en+1] == 1) en++;
		Lines.emplace(st, en, 0);
		i = en;
	}

	for(int q=0; q<Q; q++) {
		char s[10]; scanf("%s", s);
		if(s[0] == 't') {
			int ix; scanf("%d", &ix);
			Qs.emplace_back(0, ix, -1);
		}else{
			int a, b; scanf("%d%d", &a, &b);
			b = b-1;
			Qs.emplace_back(1, a, b);
		}
	}

	idx = IDX(N+1);
	dc(0, Q-1, 1);

	for(int q=0; q<Q; q++) {
		if(get<0>(Qs[q]) == 1) {
			printf("%d\n", Ans[q]);
		}
	}
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:150:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |  for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:160:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |   char s[10]; scanf("%s", s);
      |               ~~~~~^~~~~~~~~
street_lamps.cpp:162:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  162 |    int ix; scanf("%d", &ix);
      |            ~~~~~^~~~~~~~~~~
street_lamps.cpp:165:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  165 |    int a, b; scanf("%d%d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 19 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28672 KB Output is correct
6 Correct 19 ms 28544 KB Output is correct
7 Correct 19 ms 28544 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 102816 KB Output is correct
2 Correct 742 ms 106840 KB Output is correct
3 Correct 907 ms 107596 KB Output is correct
4 Correct 1461 ms 118284 KB Output is correct
5 Correct 1515 ms 126040 KB Output is correct
6 Correct 1208 ms 128080 KB Output is correct
7 Correct 721 ms 49408 KB Output is correct
8 Correct 752 ms 49492 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28928 KB Output is correct
2 Correct 20 ms 28800 KB Output is correct
3 Correct 21 ms 28800 KB Output is correct
4 Correct 21 ms 28544 KB Output is correct
5 Correct 1040 ms 170456 KB Output is correct
6 Correct 1405 ms 162264 KB Output is correct
7 Correct 1479 ms 125916 KB Output is correct
8 Correct 776 ms 49496 KB Output is correct
9 Correct 314 ms 39136 KB Output is correct
10 Correct 339 ms 41304 KB Output is correct
11 Correct 340 ms 41280 KB Output is correct
12 Correct 745 ms 49496 KB Output is correct
13 Correct 780 ms 49240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28544 KB Output is correct
2 Correct 19 ms 28672 KB Output is correct
3 Correct 20 ms 28672 KB Output is correct
4 Correct 20 ms 28800 KB Output is correct
5 Correct 1470 ms 49428 KB Output is correct
6 Correct 1358 ms 86920 KB Output is correct
7 Correct 1175 ms 122456 KB Output is correct
8 Correct 908 ms 174568 KB Output is correct
9 Correct 643 ms 129260 KB Output is correct
10 Correct 595 ms 162644 KB Output is correct
11 Correct 638 ms 129112 KB Output is correct
12 Correct 597 ms 162508 KB Output is correct
13 Correct 638 ms 128988 KB Output is correct
14 Correct 588 ms 162776 KB Output is correct
15 Correct 749 ms 43392 KB Output is correct
16 Correct 776 ms 43588 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28544 KB Output is correct
2 Correct 19 ms 28544 KB Output is correct
3 Correct 19 ms 28544 KB Output is correct
4 Correct 19 ms 28544 KB Output is correct
5 Correct 19 ms 28672 KB Output is correct
6 Correct 19 ms 28544 KB Output is correct
7 Correct 19 ms 28544 KB Output is correct
8 Correct 681 ms 102816 KB Output is correct
9 Correct 742 ms 106840 KB Output is correct
10 Correct 907 ms 107596 KB Output is correct
11 Correct 1461 ms 118284 KB Output is correct
12 Correct 1515 ms 126040 KB Output is correct
13 Correct 1208 ms 128080 KB Output is correct
14 Correct 721 ms 49408 KB Output is correct
15 Correct 752 ms 49492 KB Output is correct
16 Correct 20 ms 28928 KB Output is correct
17 Correct 20 ms 28800 KB Output is correct
18 Correct 21 ms 28800 KB Output is correct
19 Correct 21 ms 28544 KB Output is correct
20 Correct 1040 ms 170456 KB Output is correct
21 Correct 1405 ms 162264 KB Output is correct
22 Correct 1479 ms 125916 KB Output is correct
23 Correct 776 ms 49496 KB Output is correct
24 Correct 314 ms 39136 KB Output is correct
25 Correct 339 ms 41304 KB Output is correct
26 Correct 340 ms 41280 KB Output is correct
27 Correct 745 ms 49496 KB Output is correct
28 Correct 780 ms 49240 KB Output is correct
29 Correct 21 ms 28544 KB Output is correct
30 Correct 19 ms 28672 KB Output is correct
31 Correct 20 ms 28672 KB Output is correct
32 Correct 20 ms 28800 KB Output is correct
33 Correct 1470 ms 49428 KB Output is correct
34 Correct 1358 ms 86920 KB Output is correct
35 Correct 1175 ms 122456 KB Output is correct
36 Correct 908 ms 174568 KB Output is correct
37 Correct 643 ms 129260 KB Output is correct
38 Correct 595 ms 162644 KB Output is correct
39 Correct 638 ms 129112 KB Output is correct
40 Correct 597 ms 162508 KB Output is correct
41 Correct 638 ms 128988 KB Output is correct
42 Correct 588 ms 162776 KB Output is correct
43 Correct 749 ms 43392 KB Output is correct
44 Correct 776 ms 43588 KB Output is correct
45 Correct 388 ms 74428 KB Output is correct
46 Correct 445 ms 75620 KB Output is correct
47 Correct 760 ms 79712 KB Output is correct
48 Correct 1439 ms 117980 KB Output is correct
49 Correct 405 ms 42456 KB Output is correct
50 Correct 395 ms 41560 KB Output is correct
51 Correct 410 ms 42584 KB Output is correct
52 Correct 415 ms 42456 KB Output is correct
53 Correct 407 ms 43084 KB Output is correct
54 Correct 403 ms 42456 KB Output is correct