oj.uz

Submission #169545

# Submission time Handle Problem Language Result Execution time Memory
169545 2019-12-20T22:32:23 Z ZwariowanyMarcin Street Lamps (APIO19_street_lamps) C++14
20 / 100
 938 ms 145744 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 = 50000000;

int n, q;
char s[nax];

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

nod w[MAX / sizeof(nod)];
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 3 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 4616 KB Output is correct
2 Correct 546 ms 5300 KB Output is correct
3 Correct 938 ms 12916 KB Output is correct
4 Runtime error 263 ms 127132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1272 KB Output is correct
2 Correct 4 ms 1404 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 6 ms 1144 KB Output is correct
5 Runtime error 234 ms 127120 KB Execution killed with signal 11 (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 3 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 453 ms 4616 KB Output is correct
9 Correct 546 ms 5300 KB Output is correct
10 Correct 938 ms 12916 KB Output is correct
11 Runtime error 263 ms 127132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -