oj.uz

Submission #169547

# Submission time Handle Problem Language Result Execution time Memory
169547 2019-12-20T22:35:49 Z ZwariowanyMarcin Street Lamps (APIO19_street_lamps) C++14
40 / 100
 4853 ms 524292 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	
		
const int nax = 3e5 + 11;
const int pod = (1 << 19);
const int MAX = 30000000;

int n, q;
char s[nax];

struct nod {
	nod *l, *r;
	int sum;
};		

nod w[MAX];
nod *wsk = w;
nod *root[nax];

nod *alo() {
	nod *r = wsk++;
	r->sum = 0;
	return r;
}

#define mak(x) x ? x : x = alo()

void add(int x, int y, int c, nod *u, int l = 0, int r = pod - 1) {
	if(x <= l && r <= y) {
		u->sum += c;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m)
		add(x, y, c, mak(u->l), l, m);
	if(m < y)
		add(x, y, c, mak(u->r), m + 1, r);
}

int qq(int x, nod *u, int l = 0, int r = pod - 1) {
	if(l == r) return u->sum;
	int m = (l + r) / 2;
	if(x <= m)
		return u->sum + qq(x, mak(u->l), l, m);
	else
		return u->sum + qq(x, mak(u->r), m + 1, r);
}

void addf(int p, int l, int r, int c) {
	for(int i = p; i <= n; i += i & -i)
		add(l, r, c, root[i]);
}

struct gao {
	int l, r, tim;
	gao (int l, int r, int tim) : l(l), r(r), tim(tim) {}
	bool operator < (gao a) const{
		return mp(l, r) < mp(a.l, a.r);
	}
};

set <gao> secik;

int st[nax];

auto daj(int x) {
	auto it = secik.upper_bound(gao(x, 111111111, 0));
	assert(it != secik.begin());
	it--;
	return *it;
}

void akt(gao v, int czas) {
	addf(v.l, v.l, v.r, czas - v.tim);
	addf(v.r + 1, v.l, v.r, -(czas - v.tim));
}

void upd(int x, int czas) {
	st[x] ^= 1;
	if(st[x]) {
		auto L = daj(x);
		auto R = daj(x + 1);
		akt(L, czas);
		akt(R, czas);
		secik.erase(L);
		secik.erase(R);
		secik.insert(gao(L.l, R.r, czas));
	}
	else {
		auto L = daj(x);
		akt(L, czas);
		secik.insert(gao(L.l, x, czas));
		secik.insert(gao(x + 1, L.r, czas));
		secik.erase(L);
	}
}
		
int query(int a, int b) {
	int res = 0;
	for(int i = a; 0 < i; i -= i & -i)
		res += qq(b, root[i]);
	return res;
}
		
int main() {	
	scanf("%d %d", &n, &q);
	scanf("%s", s + 1);
	for(int i = 1; i <= n; ++i)
		st[i] = s[i] - '0';
	for(int i = 1; i <= n + 1;) {
		int j = i;
		while(j <= n && st[j])
			j++;
		secik.insert(gao(i, j, 0));
		i = j + 1;
	}
	for(int i = 1; i <= n + 1; ++i)
		mak(root[i]);
	for(int i = 1; i <= q; ++i) {
		scanf("%s", s);
		if(s[0] == 't') {
			int a;
			scanf("%d", &a);
			upd(a, i);
		}
		else {
			int a, b;
			scanf("%d %d", &a, &b);
			int res = query(a, b);
			auto L = daj(a);
			if(b <= L.r)
				res += i - L.tim;
			printf("%d\n", res);
		}
	}
	
	
	
	
	return 0;
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s + 1);
  ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
street_lamps.cpp:132:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 1580 KB Output is correct
2 Correct 543 ms 1964 KB Output is correct
3 Correct 999 ms 9168 KB Output is correct
4 Correct 3298 ms 313256 KB Output is correct
5 Correct 3380 ms 350680 KB Output is correct
6 Correct 3153 ms 315708 KB Output is correct
7 Correct 1800 ms 227584 KB Output is correct
8 Correct 1493 ms 210044 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1400 KB Output is correct
2 Correct 6 ms 1444 KB Output is correct
3 Correct 5 ms 1400 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 4853 ms 385504 KB Output is correct
6 Runtime error 4613 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1144 KB Output is correct
2 Correct 4 ms 1400 KB Output is correct
3 Correct 5 ms 1276 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Runtime error 1944 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 455 ms 1580 KB Output is correct
9 Correct 543 ms 1964 KB Output is correct
10 Correct 999 ms 9168 KB Output is correct
11 Correct 3298 ms 313256 KB Output is correct
12 Correct 3380 ms 350680 KB Output is correct
13 Correct 3153 ms 315708 KB Output is correct
14 Correct 1800 ms 227584 KB Output is correct
15 Correct 1493 ms 210044 KB Output is correct
16 Correct 6 ms 1400 KB Output is correct
17 Correct 6 ms 1444 KB Output is correct
18 Correct 5 ms 1400 KB Output is correct
19 Correct 3 ms 1144 KB Output is correct
20 Correct 4853 ms 385504 KB Output is correct
21 Runtime error 4613 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -