답안 #647762

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647762 2022-10-04T03:22:48 Z baojiaopisu 가로등 (APIO19_street_lamps) C++14
100 / 100
1164 ms 343076 KB
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 3e5 + 10;
const int LOG = 18;

struct SegmentTree {
	struct TrieNode {
		TrieNode* child[2];
		int sum;

		TrieNode() {
			child[0] = child[1] = nullptr;
			sum = 0;
		}
	};
	int n;
	vector<TrieNode*> node;

	SegmentTree(int _n = 0) {
		n = _n;
		node.resize(4 * n + 7);
		for(int i = 1; i <= 4 * n; i++) node[i] = new TrieNode();
	}
private:
	void addTrie(TrieNode* curr, int x, int val) {
		for(int i = LOG; i >= 0; i--) {
			int p = (x >> i & 1);
			if(curr->child[p] == nullptr) curr->child[p] = new TrieNode();
			curr = curr->child[p];
			curr->sum += val;
		}
	}

	void update(int L, int R, int lo, int hi, int u, int v, int val, int id) {
		if(L > hi || R < lo) return;
		if(lo <= L && R <= hi) {
			addTrie(node[id], u, val);
			addTrie(node[id], v + 1, -val);
			return;
		}

		int mid = (L + R) >> 1;
		update(L, mid, lo, hi, u, v, val, id << 1);
		update(mid + 1, R, lo, hi, u, v, val, id << 1 | 1);
	}

	int getTrie(TrieNode* curr, int x) {
		int ans = 0;
		for(int i = LOG; i >= 0; i--) {
			int p = (x >> i & 1);
			if(p == 1 && curr->child[0] != nullptr) ans += curr->child[0]->sum;
			if(curr->child[p] == nullptr) return ans;
			curr = curr->child[p];
		}
		return ans;
	}

	int get(int L, int R, int lo, int hi, int id) {
		int ans = getTrie(node[id], lo + 1);
		if(L == R) return ans;

		int mid = (L + R) >> 1;
		if(hi <= mid) return ans + get(L, mid, lo, hi, id << 1);
		else return ans + get(mid + 1, R, lo, hi, id << 1 | 1);
	}
public:
	void Update(int lo, int hi, int u, int v, int val) {
		update(1, n, lo, hi, u, v, val, 1);
	}

	int Get(int L, int R) {
		return get(1, n, L, R, 1);
	}
};

template <class T> struct FenwickTree {
	int n;
	vector<T> bit;

	FenwickTree(int _n = 0) {
		n = _n;
		bit.resize(n + 5);
		for(int i = 1; i <= n; i++) bit[i] = 0;
	}

	void update(int pos, T x) {
		for(int i = pos; i <= n; i += i & (-i)) bit[i] += x;
	}

	T get(int pos) {
		T ans = 0;
		for(int i = pos; i > 0; i -= i & (-i)) ans += bit[i];
		return ans;
	}
};

int state[N];

void solve() {
	int n, q; cin >> n >> q;
	set<int> zero;
	FenwickTree<int> BIT = FenwickTree<int>(n);
	for(int i = 1; i <= n; i++) {
		char c; cin >> c;
		state[i] = c - '0';
		if(!state[i]) zero.ins(i);
		BIT.update(i, state[i]);
	}

	SegmentTree IT = SegmentTree(n);

	for(int i = 1; i <= n; i++) {
		if(state[i] && !state[i - 1]) {
			int j = i;
			while(state[j + 1]) j++;
			IT.Update(i, j, i, j, -1);
			i = j;
		}
	}

	for(int i = 1; i <= q; i++) {
		string s; cin >> s;
		if(s == "toggle") {
			int id; cin >> id;
			if(state[id]) {
				int L, R;
				if(!zero.size()) {
					L = 1, R = n;
				} else {
					auto iter = zero.upper_bound(id);
					if(iter == zero.end()) R = n; else R = (*iter) - 1;
					if(iter == zero.begin()) L = 1;
					else iter--, L = (*iter) + 1;
				}

				IT.Update(id, R, L, id, i + 1);
				state[id] = 0;
				BIT.update(id, -1);
				zero.ins(id);
			} else {
				int L, R;
				zero.erase(id);
				if(!zero.size()) {
					L = 1, R = n;
				} else {
					auto iter = zero.upper_bound(id);
					if(iter == zero.end()) R = n; else R = (*iter) - 1;
					if(iter == zero.begin()) L = 1;
					else iter--, L = (*iter) + 1;
				}

				IT.Update(id, R, L, id, -i - 1);
				state[id] = 1;
				BIT.update(id, 1);
			}
		} else {
			int L, R; cin >> L >> R; R--;
			int ans = IT.Get(L, R);
			if(BIT.get(R) - BIT.get(L - 1) == R - L + 1) ans += i + 1;
			cout << ans << '\n';
		}		
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        solve();
    }
}

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:233:17: warning: unused variable 'ddd' [-Wunused-variable]
  233 |     int tc = 1, ddd = 0;
      |                 ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 1660 KB Output is correct
2 Correct 215 ms 2180 KB Output is correct
3 Correct 357 ms 10984 KB Output is correct
4 Correct 763 ms 200916 KB Output is correct
5 Correct 930 ms 283320 KB Output is correct
6 Correct 847 ms 212024 KB Output is correct
7 Correct 327 ms 64400 KB Output is correct
8 Correct 285 ms 51624 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 2 ms 1364 KB Output is correct
3 Correct 3 ms 1236 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1164 ms 343076 KB Output is correct
6 Correct 1064 ms 331072 KB Output is correct
7 Correct 876 ms 287972 KB Output is correct
8 Correct 274 ms 57468 KB Output is correct
9 Correct 101 ms 4036 KB Output is correct
10 Correct 90 ms 4304 KB Output is correct
11 Correct 109 ms 4580 KB Output is correct
12 Correct 368 ms 70172 KB Output is correct
13 Correct 295 ms 57540 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 988 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 425 ms 140208 KB Output is correct
6 Correct 645 ms 180460 KB Output is correct
7 Correct 756 ms 216444 KB Output is correct
8 Correct 1002 ms 254460 KB Output is correct
9 Correct 205 ms 4804 KB Output is correct
10 Correct 176 ms 3492 KB Output is correct
11 Correct 196 ms 4812 KB Output is correct
12 Correct 177 ms 3500 KB Output is correct
13 Correct 201 ms 4800 KB Output is correct
14 Correct 168 ms 3404 KB Output is correct
15 Correct 315 ms 70192 KB Output is correct
16 Correct 282 ms 57652 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 175 ms 1660 KB Output is correct
9 Correct 215 ms 2180 KB Output is correct
10 Correct 357 ms 10984 KB Output is correct
11 Correct 763 ms 200916 KB Output is correct
12 Correct 930 ms 283320 KB Output is correct
13 Correct 847 ms 212024 KB Output is correct
14 Correct 327 ms 64400 KB Output is correct
15 Correct 285 ms 51624 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1164 ms 343076 KB Output is correct
21 Correct 1064 ms 331072 KB Output is correct
22 Correct 876 ms 287972 KB Output is correct
23 Correct 274 ms 57468 KB Output is correct
24 Correct 101 ms 4036 KB Output is correct
25 Correct 90 ms 4304 KB Output is correct
26 Correct 109 ms 4580 KB Output is correct
27 Correct 368 ms 70172 KB Output is correct
28 Correct 295 ms 57540 KB Output is correct
29 Correct 2 ms 724 KB Output is correct
30 Correct 2 ms 852 KB Output is correct
31 Correct 2 ms 988 KB Output is correct
32 Correct 2 ms 1108 KB Output is correct
33 Correct 425 ms 140208 KB Output is correct
34 Correct 645 ms 180460 KB Output is correct
35 Correct 756 ms 216444 KB Output is correct
36 Correct 1002 ms 254460 KB Output is correct
37 Correct 205 ms 4804 KB Output is correct
38 Correct 176 ms 3492 KB Output is correct
39 Correct 196 ms 4812 KB Output is correct
40 Correct 177 ms 3500 KB Output is correct
41 Correct 201 ms 4800 KB Output is correct
42 Correct 168 ms 3404 KB Output is correct
43 Correct 315 ms 70192 KB Output is correct
44 Correct 282 ms 57652 KB Output is correct
45 Correct 88 ms 2636 KB Output is correct
46 Correct 113 ms 2932 KB Output is correct
47 Correct 373 ms 86924 KB Output is correct
48 Correct 722 ms 205360 KB Output is correct
49 Correct 104 ms 4400 KB Output is correct
50 Correct 104 ms 4368 KB Output is correct
51 Correct 104 ms 4644 KB Output is correct
52 Correct 108 ms 4980 KB Output is correct
53 Correct 106 ms 5056 KB Output is correct
54 Correct 104 ms 5012 KB Output is correct