답안 #838684

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838684 2023-08-27T15:07:30 Z fanwen 돌 무게 재기 (IZhO11_stones) C++17
100 / 100
166 ms 6052 KB
/**
 *      author : pham van sam 
 *      created : 27 August 2023 (Sunday)
 **/

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct node {
	T Max, Min;
	node(T Max = 0, T Min = 0) : Max(Max), Min(Min){}
	friend node operator + (const node &lhs, const node &rhs) {
		return node(max(lhs.Max, rhs.Max), min(lhs.Min, rhs.Min));
	}
};

template <class T> 
struct lazy_segment_tree {
	vector <node <T>> it;
	vector <T> lazy;
    int n, version = 0;

    void modify(int idx, int l, int r, T val) {
    	lazy[idx] += val;
    	it[idx].Max += val;
    	it[idx].Min += val;
    } 

    void push(int idx, int l, int r) {
        if(lazy[idx] == 0) return;
        int mid = l + r >> 1;
        modify(idx << 1, l, mid, lazy[idx]);
        modify(idx << 1 | 1, mid + 1, r, lazy[idx]);
        lazy[idx] = 0;
    }

    void update(int idx, int l, int r, int u, int v, T val) {
        if(l > v || r < u) return;
        if(l >= u && r <= v) {
            modify(idx, l, r, val);
            return;
        }
        push(idx, l, r);
        int mid = l + r >> 1;
        update(idx << 1, l, mid, u, v, val);
        update(idx << 1 | 1, mid + 1, r, u, v, val);
        it[idx] = it[idx << 1] + it[idx << 1 | 1];
    }

    node<T> get(int idx, int l, int r, int u, int v) {
        if(l > v || r < u) return node<T>(-n - 1, n + 1);
        if(l >= u && r <= v) return it[idx];
        push(idx, l, r);
        int mid = l + r >> 1;
        return get(idx << 1, l, mid, u, v) + get(idx << 1 | 1, mid + 1, r, u, v);
    }

    int find(int idx, int l, int r) {
    	if(it[idx].Max == 0 && it[idx].Min == 0) return -1;
    	if(l == r) return l;
    	push(idx, l, r);
    	int mid = l + r >> 1;
    	if(it[idx << 1 | 1].Max != 0 || it[idx << 1 | 1].Min != 0) return find(idx << 1 | 1, mid + 1, r);
    	return find(idx << 1, l, mid);
    }

public :
    
    explicit lazy_segment_tree(int n) : 
        n(n), lazy(n << 2 | 1, 0), it(n << 2 | 1) {}

    void update(int l, int r, T val) { 
        update(1, 1, n, l, r, val); 
    }

    node<T> get(int l, int r) { 
        return get(1, 1, n, l, r); 
    }

    T get(int u) {
        return get(u, u).Max;
    }

    int find() { 
    	++version;
    	return find(1, 1, n); 
    }
};

void you_make_it(void) {
	int n; cin >> n;
	lazy_segment_tree <int> it(n);
    for (int i = 1; i <= n; ++i) {
    	int x, r; cin >> x >> r;
    	it.update(1, x, (r == 1 ? 1 : -1));
    	int res = it.find();
    	if(res == -1) {
    		cout << "?\n";
    		continue;
    	}
    	if(it.get(res) > 0) {
    		cout << (it.get(1, n).Min >= 0 ? ">" : "?");
    	} else {
    		cout << (it.get(1, n).Max <= 0 ? "<" : "?");
    	}
    	cout << endl;
    }
}

signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Compilation message

stones.cpp: In instantiation of 'lazy_segment_tree<T>::lazy_segment_tree(int) [with T = int]':
stones.cpp:94:30:   required from here
stones.cpp:23:9: warning: 'lazy_segment_tree<int>::n' will be initialized after [-Wreorder]
   23 |     int n, version = 0;
      |         ^
stones.cpp:22:13: warning:   'std::vector<int> lazy_segment_tree<int>::lazy' [-Wreorder]
   22 |  vector <T> lazy;
      |             ^~~~
stones.cpp:71:14: warning:   when initialized here [-Wreorder]
   71 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~
stones.cpp:22:13: warning: 'lazy_segment_tree<int>::lazy' will be initialized after [-Wreorder]
   22 |  vector <T> lazy;
      |             ^~~~
stones.cpp:21:20: warning:   'std::vector<node<int>, std::allocator<node<int> > > lazy_segment_tree<int>::it' [-Wreorder]
   21 |  vector <node <T>> it;
      |                    ^~
stones.cpp:71:14: warning:   when initialized here [-Wreorder]
   71 |     explicit lazy_segment_tree(int n) :
      |              ^~~~~~~~~~~~~~~~~
stones.cpp: In instantiation of 'void lazy_segment_tree<T>::update(int, int, int, int, int, T) [with T = int]':
stones.cpp:75:15:   required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
stones.cpp:97:39:   required from here
stones.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid = l + r >> 1;
      |                   ~~^~~
stones.cpp: In instantiation of 'int lazy_segment_tree<T>::find(int, int, int) [with T = int]':
stones.cpp:88:17:   required from 'int lazy_segment_tree<T>::find() [with T = int]'
stones.cpp:98:24:   required from here
stones.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |      int mid = l + r >> 1;
      |                ~~^~~
stones.cpp: In instantiation of 'node<T> lazy_segment_tree<T>::get(int, int, int, int, int) [with T = int]':
stones.cpp:79:19:   required from 'node<T> lazy_segment_tree<T>::get(int, int) [with T = int]'
stones.cpp:104:27:   required from here
stones.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~
stones.cpp: In instantiation of 'void lazy_segment_tree<T>::push(int, int, int) [with T = int]':
stones.cpp:45:9:   required from 'void lazy_segment_tree<T>::update(int, int, int, int, int, T) [with T = int]'
stones.cpp:75:15:   required from 'void lazy_segment_tree<T>::update(int, int, T) [with T = int]'
stones.cpp:97:39:   required from here
stones.cpp:33:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         int mid = l + r >> 1;
      |                   ~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 15 ms 780 KB Output is correct
11 Correct 103 ms 3380 KB Output is correct
12 Correct 138 ms 5380 KB Output is correct
13 Correct 147 ms 5984 KB Output is correct
14 Correct 166 ms 5892 KB Output is correct
15 Correct 146 ms 5924 KB Output is correct
16 Correct 153 ms 5960 KB Output is correct
17 Correct 151 ms 5980 KB Output is correct
18 Correct 153 ms 6008 KB Output is correct
19 Correct 149 ms 5968 KB Output is correct
20 Correct 157 ms 5968 KB Output is correct
21 Correct 146 ms 5944 KB Output is correct
22 Correct 162 ms 5984 KB Output is correct
23 Correct 152 ms 5964 KB Output is correct
24 Correct 162 ms 5960 KB Output is correct
25 Correct 150 ms 6052 KB Output is correct