Submission #169550

#	Time	Username	Problem	Language	Result	Execution time	Memory
169550		ZwariowanyMarcin	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	4560 ms	372072 KiB

street_lamps

#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 = 40000000;

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(!u) return 0;
	if(l == r) return u->sum;
	int m = (l + r) / 2;
	if(x <= m)
		return u->sum + qq(x, u->l, l, m);
	else
		return u->sum + qq(x, 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 (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:116: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:117: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:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
street_lamps.cpp:133:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:138: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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20