Submission #838684

#	Time	Username	Problem	Language	Result	Execution time	Memory
838684		fanwen	Weighting stones (IZhO11_stones)	C++17	100 / 100	166 ms	6052 KiB

stones

/**
 *      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 (stderr)

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;
      |                   ~~^~~

• Subtask 1: 100 / 100