oj.uz

Submission #208986

# Submission time Handle Problem Language Result Execution time Memory
208986 2020-03-12T21:36:40 Z jtnydv25 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 2359 ms 298496 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, class V, int num_bits>
struct compressed_trie{
	int root;
	V sm;
	compressed_trie(){
		root = ++cnt;
		D[root].height = num_bits;
		sm = 0;
	}
	void add(T x, V 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;
		}
	}
	V order_of_key(T x){
		int node = root;
		int pos = num_bits - 1;
		V 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, 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 173 ms 291576 KB Output is correct
2 Correct 169 ms 291444 KB Output is correct
3 Correct 167 ms 291576 KB Output is correct
4 Correct 170 ms 291448 KB Output is correct
5 Correct 165 ms 291448 KB Output is correct
6 Correct 171 ms 291656 KB Output is correct
7 Correct 174 ms 291448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 292600 KB Output is correct
2 Correct 529 ms 292600 KB Output is correct
3 Correct 765 ms 292600 KB Output is correct
4 Correct 1544 ms 298488 KB Output is correct
5 Correct 1684 ms 298488 KB Output is correct
6 Correct 1675 ms 298496 KB Output is correct
7 Correct 469 ms 293988 KB Output is correct
8 Correct 464 ms 295032 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 291576 KB Output is correct
2 Correct 176 ms 291576 KB Output is correct
3 Correct 174 ms 291576 KB Output is correct
4 Correct 171 ms 291560 KB Output is correct
5 Correct 2111 ms 297724 KB Output is correct
6 Correct 2012 ms 297984 KB Output is correct
7 Correct 1592 ms 297976 KB Output is correct
8 Correct 461 ms 295032 KB Output is correct
9 Correct 305 ms 292600 KB Output is correct
10 Correct 308 ms 292472 KB Output is correct
11 Correct 307 ms 292728 KB Output is correct
12 Correct 469 ms 293628 KB Output is correct
13 Correct 464 ms 295092 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 291576 KB Output is correct
2 Correct 178 ms 291576 KB Output is correct
3 Correct 170 ms 291576 KB Output is correct
4 Correct 170 ms 291576 KB Output is correct
5 Correct 633 ms 298488 KB Output is correct
6 Correct 1102 ms 298268 KB Output is correct
7 Correct 1566 ms 298104 KB Output is correct
8 Correct 2359 ms 297760 KB Output is correct
9 Correct 537 ms 291832 KB Output is correct
10 Correct 479 ms 291576 KB Output is correct
11 Correct 544 ms 291704 KB Output is correct
12 Correct 501 ms 291560 KB Output is correct
13 Correct 539 ms 291832 KB Output is correct
14 Correct 489 ms 291576 KB Output is correct
15 Correct 461 ms 293624 KB Output is correct
16 Correct 470 ms 295032 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 291576 KB Output is correct
2 Correct 169 ms 291444 KB Output is correct
3 Correct 167 ms 291576 KB Output is correct
4 Correct 170 ms 291448 KB Output is correct
5 Correct 165 ms 291448 KB Output is correct
6 Correct 171 ms 291656 KB Output is correct
7 Correct 174 ms 291448 KB Output is correct
8 Correct 449 ms 292600 KB Output is correct
9 Correct 529 ms 292600 KB Output is correct
10 Correct 765 ms 292600 KB Output is correct
11 Correct 1544 ms 298488 KB Output is correct
12 Correct 1684 ms 298488 KB Output is correct
13 Correct 1675 ms 298496 KB Output is correct
14 Correct 469 ms 293988 KB Output is correct
15 Correct 464 ms 295032 KB Output is correct
16 Correct 172 ms 291576 KB Output is correct
17 Correct 176 ms 291576 KB Output is correct
18 Correct 174 ms 291576 KB Output is correct
19 Correct 171 ms 291560 KB Output is correct
20 Correct 2111 ms 297724 KB Output is correct
21 Correct 2012 ms 297984 KB Output is correct
22 Correct 1592 ms 297976 KB Output is correct
23 Correct 461 ms 295032 KB Output is correct
24 Correct 305 ms 292600 KB Output is correct
25 Correct 308 ms 292472 KB Output is correct
26 Correct 307 ms 292728 KB Output is correct
27 Correct 469 ms 293628 KB Output is correct
28 Correct 464 ms 295092 KB Output is correct
29 Correct 168 ms 291576 KB Output is correct
30 Correct 178 ms 291576 KB Output is correct
31 Correct 170 ms 291576 KB Output is correct
32 Correct 170 ms 291576 KB Output is correct
33 Correct 633 ms 298488 KB Output is correct
34 Correct 1102 ms 298268 KB Output is correct
35 Correct 1566 ms 298104 KB Output is correct
36 Correct 2359 ms 297760 KB Output is correct
37 Correct 537 ms 291832 KB Output is correct
38 Correct 479 ms 291576 KB Output is correct
39 Correct 544 ms 291704 KB Output is correct
40 Correct 501 ms 291560 KB Output is correct
41 Correct 539 ms 291832 KB Output is correct
42 Correct 489 ms 291576 KB Output is correct
43 Correct 461 ms 293624 KB Output is correct
44 Correct 470 ms 295032 KB Output is correct
45 Correct 281 ms 292088 KB Output is correct
46 Correct 344 ms 291704 KB Output is correct
47 Correct 836 ms 293752 KB Output is correct
48 Correct 1455 ms 298004 KB Output is correct
49 Correct 305 ms 292216 KB Output is correct
50 Correct 306 ms 292088 KB Output is correct
51 Correct 310 ms 292216 KB Output is correct
52 Correct 313 ms 292216 KB Output is correct
53 Correct 319 ms 292088 KB Output is correct
54 Correct 321 ms 292100 KB Output is correct