oj.uz

답안 #292093

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292093 2020-09-06T10:15:48 Z kajebiii 가로등 (APIO19_street_lamps) C++17
20 / 100
 545 ms 27992 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>;

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<ti> &dels, ti del, int q) {
	get<2>(del) = q - get<2>(del) + 1;
	dels.push_back(del);
}
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);
		}
	}

	vector<ti> dels;
	vector<ti> queries;
	for(int q=0; q<Q; q++) {
		char s[10]; scanf("%s", s);
		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];
			queries.emplace_back(a, b, q);
		}
	}
	sort(ALL(dels));
	sort(ALL(queries));
	int delsIx = 0;
	IDX idx = IDX(N+1);
	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, v; tie(x, y, v) = dels[delsIx++];
			idx.add(y, v);
		}

		int now = idx.getSum(b, N);
		//if(now != 0) printf(">> [%d] %d %d += %d\n", q, a, b, now);
		Ans[q] += now;
	}
	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) {
			//if(q-t+1 != 0) printf("<< [%d] %d %d += %d (%d)\n", q, a, b, q-t+1, t);
			Ans[q] += q - t + 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:53:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  for(int i=1; i<=N; i++) scanf("%1d", &Nr[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:63:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   char s[10]; scanf("%s", s);
      |               ~~~~~^~~~~~~~~
street_lamps.cpp:65:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |    int ix; scanf("%d", &ix);
      |            ~~~~~^~~~~~~~~~~
street_lamps.cpp:68:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |    int a, b; scanf("%d%d", &a, &b);
      |              ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:77:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   char s[10]; scanf("%s", s);
      |               ~~~~~^~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 286 ms 13252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 408 ms 25408 KB Output is correct
6 Correct 448 ms 27992 KB Output is correct
7 Correct 502 ms 26160 KB Output is correct
8 Correct 545 ms 23256 KB Output is correct
9 Correct 338 ms 14428 KB Output is correct
10 Correct 282 ms 16080 KB Output is correct
11 Correct 288 ms 14296 KB Output is correct
12 Correct 279 ms 15960 KB Output is correct
13 Correct 293 ms 14296 KB Output is correct
14 Correct 278 ms 16088 KB Output is correct
15 Correct 347 ms 20700 KB Output is correct
16 Correct 356 ms 22028 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -