oj.uz

Submission #208984

# Submission time Handle Problem Language Result Execution time Memory
208984 2020-03-12T21:09:03 Z jtnydv25 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2550 ms 407428 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int M = 1.2e7;
template<class T>
struct Data{
	int child[2], bits[2], height;
	T val;
	Data(){
		child[0] = bits[0] = child[1] = bits[1] = val = height = 0;
	}
};
Data<ll> D[M];
// int child[M][2], bits[M][2], val[M], height[M];
const int MAX_BITS = 31;
int cnt = 0;
inline int clz(int N) {
    return N ? 31 - __builtin_clz(N) : -1;
}

template<int num_bits>
struct compressed_trie{
	int root;
	ll sm;
	compressed_trie(){
		root = ++cnt;
		D[root].height = num_bits;
		sm = 0;
	}
	void add(int x, int v){
		sm += v;
		int node = root;
		int pos = num_bits - 1;
		for(; ; ){
			Data<ll> & d = D[node];
			d.val += v;
			if(pos < 0) return;
			int dir = x >> pos & 1;
			if(!d.child[dir]){
				d.child[dir] = ++cnt;
				D[cnt].val += v;
				d.bits[dir] = x;
				return;
			}
			int y = d.bits[dir];
			int nxt = d.child[dir];
			int nxtH = D[nxt].height;
			y <<= (nxtH);
 
			int diff = clz(x^y);
 
			if(diff < nxtH){
				node = nxt;
				pos = nxtH - 1;
				x &= ((1<<nxtH) - 1);
				continue;
			}
 
			int yside = y >> diff & 1;
			int xside = x >> diff & 1;
 
			d.child[dir] = ++cnt;
			d.bits[dir] = x >> (diff + 1);
			D[cnt].val = D[nxt].val + v;
			D[cnt].height = diff + 1;
 
			D[cnt].child[yside] = nxt;
			D[cnt].bits[yside] = (y >> nxtH) & ( (1 << (diff + 1 - nxtH)) - 1);
			D[cnt].bits[xside] = x & ((1 << (diff + 1)) - 1);
			D[cnt].child[xside] = cnt + 1; ++cnt;
			D[cnt].val = v;
			return;
		}
	}
	ll order_of_key(int x){
		int node = root;
		int pos = num_bits - 1;
		ll ret = 0;
		bool to_print = (x == 11);
		for(; pos >= 0; ){
			int dir = x >> pos & 1;
			Data<ll> & d = D[node];	
			if(dir) ret += D[d.child[0]].val;
			if(!d.child[dir]){
				return ret;
			}
			int y = d.bits[dir];
			int nxt = d.child[dir];
			int nxtH = D[nxt].height;
			y <<= (nxtH);
 
			int diff =  clz(x^y);
 
			if(diff < nxtH){
				node = nxt;
				pos = nxtH - 1;
				x &= ((1<<nxtH) - 1);
				continue;
			}
			int xside = x >> diff & 1;
			if(xside) ret += D[nxt].val;
			return ret;
		}
		return ret;
	}
	void insert(int x){
		add(x, 1);
	}
};

const int N = 300005;
compressed_trie<20> tree[4 * N];
int n, q;

void add(int l, int r, int x, int s = 1, int e = n, int ind = 1){
	if(s > l || e < l) return;
	tree[ind].add(r, x);
	if(s == e) return;
	int mid = (s + e) >> 1;
	add(l, r, x, s, mid, ind << 1);
	add(l, r, x, mid + 1, e, ind << 1 | 1);
}

ll get(int a, int b, int s = 1, int e = n, int ind = 1){
	if(s > a) return 0;
	if(e <= a) return tree[ind].sm - tree[ind].order_of_key(b);
	int mid = (s + e) >> 1;
	return get(a, b, s, mid, ind << 1) + get(a, b, mid + 1, e, ind << 1 | 1);
}

set<pair<pii, int>> currIntervals;
char s[N];
int curr[N];
pair<pii, int> get(int p){
	auto it = currIntervals.upper_bound({{p + 1, -1}, -1});
	it--; return *it;
}

int main(){
	sd(n); sd(q);
	scanf("%s", s + 1);
	for(int i = 1; i <= n; i++) curr[i] = s[i] == '1';
	for(int i = 1; i <= n;){
		if(s[i] == '1'){
			int l = i;
			while(i <= n && s[i] == '1') i++;
			currIntervals.insert({{l, i - 1}, 0});
		}
		i++;
	}

	for(int t = 1; t <= q; t++){
		scanf("%s", s);
		if(s[0] == 't'){
			int i; sd(i);
			if(curr[i]){
				auto it = get(i);
				int l = it.F.F, r = it.F.S, _t = it.S;
				add(l, r, t - _t);
				currIntervals.erase(it);
				if(l <= i - 1) currIntervals.insert({{l, i - 1}, t});
				if(r > i) currIntervals.insert({{i + 1, r}, t});
			} else{
				int l = i, r = i;
				if(curr[i - 1]){
					auto it = get(i - 1);
					l = it.F.F;
					add(l, it.F.S, t - it.S);
					currIntervals.erase(it);
				}
				if(curr[i + 1]){
					auto it = get(i + 1);
					r = it.F.S;
					add(it.F.F, r, t - it.S);
					currIntervals.erase(it);
				}
				currIntervals.insert({{l, r}, t});
			}
			curr[i] ^= 1;
		} else{
			int a, b; sd(a); sd(b); b--;
			int ans = get(a, b);
			if(curr[a]){
				auto it = get(a);
				if(it.F.S >= b) ans += t - it.S;
			}
			printf("%d\n", ans);
		}
	}
}

Compilation message

street_lamps.cpp: In instantiation of 'long long int compressed_trie<num_bits>::order_of_key(int) [with int num_bits = 20]':
street_lamps.cpp:173:59:   required from here
street_lamps.cpp:126:8: warning: unused variable 'to_print' [-Wunused-variable]
   bool to_print = (x == 11);
        ^~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
street_lamps.cpp:187:2: note: in expansion of macro 'sd'
  sd(n); sd(q);
  ^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
street_lamps.cpp:187:9: note: in expansion of macro 'sd'
  sd(n); sd(q);
         ^~
street_lamps.cpp:188: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:200:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
   ~~~~~^~~~~~~~~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
street_lamps.cpp:202:11: note: in expansion of macro 'sd'
    int i; sd(i);
           ^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
street_lamps.cpp:228:14: note: in expansion of macro 'sd'
    int a, b; sd(a); sd(b); b--;
              ^~
street_lamps.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define sd(x) scanf("%d", &(x))
               ~~~~~^~~~~~~~~~~~
street_lamps.cpp:228:21: note: in expansion of macro 'sd'
    int a, b; sd(a); sd(b); b--;
                     ^~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 394972 KB Output is correct
2 Correct 232 ms 394864 KB Output is correct
3 Correct 214 ms 394888 KB Output is correct
4 Correct 211 ms 394872 KB Output is correct
5 Correct 208 ms 394780 KB Output is correct
6 Correct 221 ms 394868 KB Output is correct
7 Correct 213 ms 394876 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 396024 KB Output is correct
2 Correct 562 ms 395768 KB Output is correct
3 Correct 851 ms 396016 KB Output is correct
4 Correct 1695 ms 401804 KB Output is correct
5 Correct 1853 ms 407428 KB Output is correct
6 Correct 1892 ms 406828 KB Output is correct
7 Correct 520 ms 402940 KB Output is correct
8 Correct 547 ms 404364 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 394900 KB Output is correct
2 Correct 222 ms 394872 KB Output is correct
3 Correct 234 ms 394872 KB Output is correct
4 Correct 228 ms 395000 KB Output is correct
5 Correct 2277 ms 401528 KB Output is correct
6 Correct 2180 ms 406304 KB Output is correct
7 Correct 1755 ms 406632 KB Output is correct
8 Correct 543 ms 404300 KB Output is correct
9 Correct 340 ms 398456 KB Output is correct
10 Correct 353 ms 398940 KB Output is correct
11 Correct 362 ms 398988 KB Output is correct
12 Correct 523 ms 402840 KB Output is correct
13 Correct 533 ms 404360 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 394824 KB Output is correct
2 Correct 215 ms 394872 KB Output is correct
3 Correct 214 ms 394872 KB Output is correct
4 Correct 210 ms 394872 KB Output is correct
5 Correct 696 ms 401784 KB Output is correct
6 Correct 1179 ms 407100 KB Output is correct
7 Correct 1714 ms 406144 KB Output is correct
8 Correct 2550 ms 405384 KB Output is correct
9 Correct 580 ms 398456 KB Output is correct
10 Correct 522 ms 397920 KB Output is correct
11 Correct 588 ms 398456 KB Output is correct
12 Correct 535 ms 397836 KB Output is correct
13 Correct 573 ms 398376 KB Output is correct
14 Correct 539 ms 397828 KB Output is correct
15 Correct 529 ms 403032 KB Output is correct
16 Correct 536 ms 404240 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 394972 KB Output is correct
2 Correct 232 ms 394864 KB Output is correct
3 Correct 214 ms 394888 KB Output is correct
4 Correct 211 ms 394872 KB Output is correct
5 Correct 208 ms 394780 KB Output is correct
6 Correct 221 ms 394868 KB Output is correct
7 Correct 213 ms 394876 KB Output is correct
8 Correct 485 ms 396024 KB Output is correct
9 Correct 562 ms 395768 KB Output is correct
10 Correct 851 ms 396016 KB Output is correct
11 Correct 1695 ms 401804 KB Output is correct
12 Correct 1853 ms 407428 KB Output is correct
13 Correct 1892 ms 406828 KB Output is correct
14 Correct 520 ms 402940 KB Output is correct
15 Correct 547 ms 404364 KB Output is correct
16 Correct 211 ms 394900 KB Output is correct
17 Correct 222 ms 394872 KB Output is correct
18 Correct 234 ms 394872 KB Output is correct
19 Correct 228 ms 395000 KB Output is correct
20 Correct 2277 ms 401528 KB Output is correct
21 Correct 2180 ms 406304 KB Output is correct
22 Correct 1755 ms 406632 KB Output is correct
23 Correct 543 ms 404300 KB Output is correct
24 Correct 340 ms 398456 KB Output is correct
25 Correct 353 ms 398940 KB Output is correct
26 Correct 362 ms 398988 KB Output is correct
27 Correct 523 ms 402840 KB Output is correct
28 Correct 533 ms 404360 KB Output is correct
29 Correct 219 ms 394824 KB Output is correct
30 Correct 215 ms 394872 KB Output is correct
31 Correct 214 ms 394872 KB Output is correct
32 Correct 210 ms 394872 KB Output is correct
33 Correct 696 ms 401784 KB Output is correct
34 Correct 1179 ms 407100 KB Output is correct
35 Correct 1714 ms 406144 KB Output is correct
36 Correct 2550 ms 405384 KB Output is correct
37 Correct 580 ms 398456 KB Output is correct
38 Correct 522 ms 397920 KB Output is correct
39 Correct 588 ms 398456 KB Output is correct
40 Correct 535 ms 397836 KB Output is correct
41 Correct 573 ms 398376 KB Output is correct
42 Correct 539 ms 397828 KB Output is correct
43 Correct 529 ms 403032 KB Output is correct
44 Correct 536 ms 404240 KB Output is correct
45 Correct 322 ms 397260 KB Output is correct
46 Correct 396 ms 397376 KB Output is correct
47 Correct 938 ms 400472 KB Output is correct
48 Correct 1554 ms 406460 KB Output is correct
49 Correct 385 ms 398972 KB Output is correct
50 Correct 361 ms 398864 KB Output is correct
51 Correct 376 ms 399156 KB Output is correct
52 Correct 373 ms 399352 KB Output is correct
53 Correct 375 ms 399352 KB Output is correct
54 Correct 372 ms 399480 KB Output is correct