oj.uz

Submission #337634

# Submission time Handle Problem Language Result Execution time Memory
337634 2020-12-21T10:02:41 Z talant117408 Weighting stones (IZhO11_stones) C++17
100 / 100
 75 ms 5656 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 1e5+7;
int tree[2][N*4], lz[2][N*4];

void push(int v, int l, int r){
    tree[0][v] += lz[0][v];
    tree[1][v] += lz[1][v];
    if(l != r){
        lz[0][v<<1] += lz[0][v];
        lz[0][(v<<1)+1] += lz[0][v];
        lz[1][v<<1] += lz[1][v];
        lz[1][(v<<1)+1] += lz[1][v];
    }
    lz[0][v] = lz[1][v] = 0;
}

void update(int v, int l, int r, int ql, int qr, int val){
    push(v, l, r);
    if(l > qr || ql > r) return ;
    if(ql <= l && r <= qr){
        tree[0][v] += val;
        tree[1][v] += val;
        if(l != r){
            lz[0][v<<1] += val;
            lz[0][(v<<1)+1] += val;
            lz[1][v<<1] += val;
            lz[1][(v<<1)+1] += val;
        }
        return ;
    }
    int mid = (l+r) >> 1;
    update(v<<1, l, mid, ql, qr, val);
    update((v<<1)+1, mid+1, r, ql, qr, val);
    tree[0][v] = min(tree[0][v<<1], tree[0][(v<<1)+1]);
    tree[1][v] = max(tree[1][v<<1], tree[1][(v<<1)+1]);
}

int main(){
    do_not_disturb
    
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x, type;
        cin >> x >> type;
        if(type == 1)
            update(1, 1, n, 1, x, 1);
        else update(1, 1, n, 1, x, -1);
        auto fi = tree[1][1], sc = tree[0][1];
        if(fi > 0){
            if(sc >= 0) cout << ">" << endl;
            else cout << "?" << endl;
        }
        else{
            if(sc <= 0) cout << "<" << endl;
            else cout << "?" << endl;
        }
    }
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 6 ms 1004 KB Output is correct
11 Correct 43 ms 2924 KB Output is correct
12 Correct 75 ms 5356 KB Output is correct
13 Correct 68 ms 5656 KB Output is correct
14 Correct 68 ms 5484 KB Output is correct
15 Correct 67 ms 5484 KB Output is correct
16 Correct 67 ms 5484 KB Output is correct
17 Correct 67 ms 5484 KB Output is correct
18 Correct 68 ms 5484 KB Output is correct
19 Correct 70 ms 5484 KB Output is correct
20 Correct 68 ms 5484 KB Output is correct
21 Correct 68 ms 5484 KB Output is correct
22 Correct 67 ms 5484 KB Output is correct
23 Correct 69 ms 5484 KB Output is correct
24 Correct 68 ms 5412 KB Output is correct
25 Correct 67 ms 5476 KB Output is correct