oj.uz

Submission #51985

# Submission time Handle Problem Language Result Execution time Memory
51985 2018-06-22T21:50:49 Z FLDutchman Weighting stones (IZhO11_stones) C++14
100 / 100
 291 ms 21572 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long
#define FOR(i, l, r) for(int i = l; i < r; i++)
#define snd second
#define fst first
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

vi tmin, tmax, lazy;
int N;

void update(int l, int r, int v, int lb, int rb, int n = 1){
    //cout << lb << " " << rb << " " << n << endl;
    if(l <= lb and rb <= r){
        lazy[n] += v; tmin[n] += v; tmax[n] += v;
        return;
    }

    int mb = (lb+rb)/2;
    if(lazy[n] != 0){
        update(lb, rb, lazy[n], lb, mb, n<<1);
        update(lb, rb, lazy[n], mb, rb, n<<1|1);
        lazy[n] = 0;
    }

    if(l < mb) update(l, r, v, lb, mb, n<<1);
    if(r > mb) update(l, r, v, mb, rb, n<<1|1);
    tmin[n] = min(tmin[2*n], tmin[2*n+1]);
    tmax[n] = max(tmax[2*n], tmax[2*n+1]);
}

signed main(){
    cin >> N;
    //N = 100; 
    tmin.assign(4*N+5, 0); 
    tmax.assign(4*N+5, 0); 
    lazy.assign(4*N+5, 0);
    /*update(0, 10, 2, 0, N);
    update(2, 20, -1, 0, N);
    update(0, 10, 2, 0, N);
    cout << tmin[1] << endl;
    cout << tmax[1] << endl;*/
    FOR(i, 0, N){
        int R, S;
        cin >> R >> S;
        update(0, R, 2*S-3, 0, N);
        //cout << tmin[1] << " " << tmax[1] << endl;
        if(tmin[1] <= 0 and tmax[1] <= 0) cout << ">" << endl;
        else if(tmin[1] >= 0 and tmax[1] >= 0) cout << "<" << endl;
        else cout << "?" << endl;
    }

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 472 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 3 ms 516 KB Output is correct
7 Correct 4 ms 568 KB Output is correct
8 Correct 5 ms 708 KB Output is correct
9 Correct 5 ms 772 KB Output is correct
10 Correct 30 ms 1580 KB Output is correct
11 Correct 152 ms 6764 KB Output is correct
12 Correct 251 ms 10588 KB Output is correct
13 Correct 251 ms 12388 KB Output is correct
14 Correct 266 ms 12952 KB Output is correct
15 Correct 257 ms 13724 KB Output is correct
16 Correct 238 ms 14624 KB Output is correct
17 Correct 291 ms 15396 KB Output is correct
18 Correct 238 ms 16288 KB Output is correct
19 Correct 238 ms 16940 KB Output is correct
20 Correct 272 ms 17712 KB Output is correct
21 Correct 241 ms 18488 KB Output is correct
22 Correct 236 ms 19128 KB Output is correct
23 Correct 234 ms 19900 KB Output is correct
24 Correct 244 ms 20676 KB Output is correct
25 Correct 287 ms 21572 KB Output is correct