oj.uz

Submission #208985

# Submission time Handle Problem Language Result Execution time Memory
208985 2020-03-12T21:34:07 Z jtnydv25 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2414 ms 312296 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<int> D[M];
int cnt = 0;

inline int clz(int N) {
    return N ? 31 - __builtin_clz(N) : -1;
}

template<class T, int num_bits>
struct compressed_trie{
	int root;
	ll sm;
	compressed_trie(){
		root = ++cnt;
		D[root].height = num_bits;
		sm = 0;
	}
	void add(T x, int v){
		sm += v;
		int node = root;
		int pos = num_bits - 1;
		for(; ; ){
			Data<T> & 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;
			}
			T 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 &= ((T(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) & ( (T(1) << (diff + 1 - nxtH)) - 1);
			D[cnt].bits[xside] = x & ((T(1) << (diff + 1)) - 1);
			D[cnt].child[xside] = cnt + 1; ++cnt;
			D[cnt].val = v;
			return;
		}
	}
	ll order_of_key(T x){
		int node = root;
		int pos = num_bits - 1;
		ll ret = 0;
		for(; pos >= 0; ){
			int dir = x >> pos & 1;
			Data<T> & d = D[node];	
			if(dir) ret += D[d.child[0]].val;
			if(!d.child[dir]){
				return ret;
			}
			T 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 &= ((T(1)<<nxtH) - 1);
				continue;
			}
			if(x >> diff & 1) ret += D[nxt].val;
			return ret;
		}
		return ret;
	}
	void insert(T x){
		add(x, 1);
	}
};

const int N = 300005;
compressed_trie<int, 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 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:184: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:184:9: note: in expansion of macro 'sd'
  sd(n); sd(q);
         ^~
street_lamps.cpp:185: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:197: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:199: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:225: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:225: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 176 ms 300920 KB Output is correct
2 Correct 189 ms 300920 KB Output is correct
3 Correct 177 ms 300980 KB Output is correct
4 Correct 169 ms 300920 KB Output is correct
5 Correct 177 ms 300920 KB Output is correct
6 Correct 174 ms 301048 KB Output is correct
7 Correct 172 ms 300924 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 305144 KB Output is correct
2 Correct 510 ms 301816 KB Output is correct
3 Correct 772 ms 302080 KB Output is correct
4 Correct 1578 ms 307832 KB Output is correct
5 Correct 1766 ms 312296 KB Output is correct
6 Correct 1758 ms 312184 KB Output is correct
7 Correct 495 ms 307064 KB Output is correct
8 Correct 506 ms 308344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 300920 KB Output is correct
2 Correct 176 ms 301132 KB Output is correct
3 Correct 172 ms 300920 KB Output is correct
4 Correct 176 ms 300920 KB Output is correct
5 Correct 2221 ms 311800 KB Output is correct
6 Correct 2087 ms 311312 KB Output is correct
7 Correct 1644 ms 311044 KB Output is correct
8 Correct 502 ms 308088 KB Output is correct
9 Correct 315 ms 304632 KB Output is correct
10 Correct 326 ms 304892 KB Output is correct
11 Correct 333 ms 305144 KB Output is correct
12 Correct 492 ms 306624 KB Output is correct
13 Correct 510 ms 307508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 300920 KB Output is correct
2 Correct 176 ms 300920 KB Output is correct
3 Correct 173 ms 300920 KB Output is correct
4 Correct 175 ms 300920 KB Output is correct
5 Correct 667 ms 307704 KB Output is correct
6 Correct 1130 ms 310136 KB Output is correct
7 Correct 1627 ms 309756 KB Output is correct
8 Correct 2414 ms 309160 KB Output is correct
9 Correct 576 ms 303112 KB Output is correct
10 Correct 499 ms 302840 KB Output is correct
11 Correct 546 ms 303096 KB Output is correct
12 Correct 493 ms 302712 KB Output is correct
13 Correct 560 ms 302840 KB Output is correct
14 Correct 497 ms 302584 KB Output is correct
15 Correct 473 ms 304376 KB Output is correct
16 Correct 503 ms 305528 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 300920 KB Output is correct
2 Correct 189 ms 300920 KB Output is correct
3 Correct 177 ms 300980 KB Output is correct
4 Correct 169 ms 300920 KB Output is correct
5 Correct 177 ms 300920 KB Output is correct
6 Correct 174 ms 301048 KB Output is correct
7 Correct 172 ms 300924 KB Output is correct
8 Correct 447 ms 305144 KB Output is correct
9 Correct 510 ms 301816 KB Output is correct
10 Correct 772 ms 302080 KB Output is correct
11 Correct 1578 ms 307832 KB Output is correct
12 Correct 1766 ms 312296 KB Output is correct
13 Correct 1758 ms 312184 KB Output is correct
14 Correct 495 ms 307064 KB Output is correct
15 Correct 506 ms 308344 KB Output is correct
16 Correct 176 ms 300920 KB Output is correct
17 Correct 176 ms 301132 KB Output is correct
18 Correct 172 ms 300920 KB Output is correct
19 Correct 176 ms 300920 KB Output is correct
20 Correct 2221 ms 311800 KB Output is correct
21 Correct 2087 ms 311312 KB Output is correct
22 Correct 1644 ms 311044 KB Output is correct
23 Correct 502 ms 308088 KB Output is correct
24 Correct 315 ms 304632 KB Output is correct
25 Correct 326 ms 304892 KB Output is correct
26 Correct 333 ms 305144 KB Output is correct
27 Correct 492 ms 306624 KB Output is correct
28 Correct 510 ms 307508 KB Output is correct
29 Correct 176 ms 300920 KB Output is correct
30 Correct 176 ms 300920 KB Output is correct
31 Correct 173 ms 300920 KB Output is correct
32 Correct 175 ms 300920 KB Output is correct
33 Correct 667 ms 307704 KB Output is correct
34 Correct 1130 ms 310136 KB Output is correct
35 Correct 1627 ms 309756 KB Output is correct
36 Correct 2414 ms 309160 KB Output is correct
37 Correct 576 ms 303112 KB Output is correct
38 Correct 499 ms 302840 KB Output is correct
39 Correct 546 ms 303096 KB Output is correct
40 Correct 493 ms 302712 KB Output is correct
41 Correct 560 ms 302840 KB Output is correct
42 Correct 497 ms 302584 KB Output is correct
43 Correct 473 ms 304376 KB Output is correct
44 Correct 503 ms 305528 KB Output is correct
45 Correct 287 ms 302072 KB Output is correct
46 Correct 342 ms 301816 KB Output is correct
47 Correct 872 ms 303992 KB Output is correct
48 Correct 1478 ms 307960 KB Output is correct
49 Correct 320 ms 302072 KB Output is correct
50 Correct 333 ms 301944 KB Output is correct
51 Correct 326 ms 302008 KB Output is correct
52 Correct 334 ms 301816 KB Output is correct
53 Correct 318 ms 301688 KB Output is correct
54 Correct 318 ms 301560 KB Output is correct