oj.uz

Submission #876818

# Submission time Handle Problem Language Result Execution time Memory
876818 2023-11-22T11:39:41 Z VahanAbraham Weighting stones (IZhO11_stones) C++14
100 / 100
 161 ms 7732 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 300005;
const ll oo = 1000000000000000, MOD = 1000000007;

struct str {
    int mn, sm;
};

int sz = 1;
str t[3 * N][3];

void init(int n) {
    while (sz < n) {
        sz *= 2;
    }
}

void seet1(int l, int r, int i, int val, int lx, int rx, int x) {
    if (lx > r || rx < l) {
        return;
    }
    if (l <= lx && rx <= r) {
        t[x][i].sm += val;
        t[x][i].mn += val;
        return;
    }
    int m = (lx + rx) / 2;
    seet1(l, r, i,val, lx, m, 2 * x);
    seet1(l, r, i,val, m + 1, rx, 2 * x + 1);
    t[x][i].mn = min(t[2 * x][i].mn, t[2 * x + 1][i].mn);
    t[x][i].mn += t[x][i].sm;
}

void solve() {
    int q;
    cin >> q;
    int y = 0, mx = 0;
    init(q);
    while (q--) {
        int r, s;
        cin >> r >> s;
        if (r > mx) {
            mx = r, y = s;
        }
        if (s == 2) {
            seet1(1, r, 1,1, 1, sz, 1);
            seet1(1, r, 2, -1, 1, sz, 1);
        }
        else {
            seet1(1, r, 2, 1,1,sz, 1);
            seet1(1,r, 1,-1, 1, sz, 1);
        }
        if (y == 2) {
            if (t[1][1].mn >= 0) {
                cout << "<" << endl;
            }
            else {
                cout << "?" << endl;
            }
        }
        else {
            if (t[1][2].mn >= 0) {
                cout << ">" << endl;
            }
            else {
                cout << "?" << endl;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 14 ms 2692 KB Output is correct
11 Correct 90 ms 5348 KB Output is correct
12 Correct 145 ms 6992 KB Output is correct
13 Correct 149 ms 7252 KB Output is correct
14 Correct 156 ms 7284 KB Output is correct
15 Correct 159 ms 7588 KB Output is correct
16 Correct 150 ms 7540 KB Output is correct
17 Correct 161 ms 7732 KB Output is correct
18 Correct 160 ms 7248 KB Output is correct
19 Correct 156 ms 7300 KB Output is correct
20 Correct 155 ms 7696 KB Output is correct
21 Correct 150 ms 7508 KB Output is correct
22 Correct 150 ms 7532 KB Output is correct
23 Correct 156 ms 7300 KB Output is correct
24 Correct 158 ms 7208 KB Output is correct
25 Correct 159 ms 7504 KB Output is correct