Submission #876818

#	Time	Username	Problem	Language	Result	Execution time	Memory
876818		VahanAbraham	Weighting stones (IZhO11_stones)	C++14	100 / 100	161 ms	7732 KiB

stones

#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 / 100