oj.uz

Submission #309256

# Submission time Handle Problem Language Result Execution time Memory
309256 2020-10-03T02:05:58 Z jainbot27 Wall (IOI14_wall) C++17
100 / 100
 1238 ms 69748 KB 
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int mn[1<<22], mx[1<<22];
void apply_op(int i, int l, int r){
    mn[i]=min(max(mn[i], l), r);
    mx[i]=min(max(mx[i], l), r);
}
void propogate(int i){
    apply_op(2*i+1, mn[i], mx[i]);
    apply_op(2*i+2, mn[i], mx[i]);
    mn[i] = 0, mx[i] = MOD;
}
void update(int l, int r, int xl, int xr, int i, int low, int high){
    if(r < xl || l > xr){
        return;
    }
    if(l <= xl && xr <= r){
        apply_op(i, low, high);
        return;
    }
    propogate(i);
    int m = (xl+xr)/2;
    update(l, r, xl, m, i*2+1, low, high);
    update(l, r, m+1, xr, i*2+2, low, high);
}
int query(int i, int pos,  int xl, int xr){
    if(xl == xr){
        assert(pos == xl);
        return mn[i];
    }
    propogate(i);
    int m = (xl+xr)/2;
    if(pos <= m){
        return query(i*2+1, pos, xl, m);
    }
    else{
        return query(i*2+2, pos, m+1, xr);
    }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalheight[]){
    F0R(i, k){
        op[i]--;
        update(left[i], right[i], 0, n-1, 0, op[i]==0?height[i]:0, op[i]==1?height[i]:MOD);
    }
    F0R(i, n){
        finalheight[i] = query(0, i, 0, n-1);
    }
}

// int main(){
//     int op[] = {1, 2, 1, 2};
//     int left[] = {0, 2, 1, 4};
//     int right[] = {3, 3, 4, 4};
//     int n = 5;
//     int k = 4;
//     int height[] = {5, 1, 9, 3};
//     int finalheight[] = {0, 0, 0, 0, 0};
//     buildWall(n, k, op, left, right, height, finalheight);
//     F0R(i, n){
//         cout << finalheight[i] << nl;
//     }
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 768 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 7 ms 768 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 174 ms 8184 KB Output is correct
3 Correct 198 ms 4260 KB Output is correct
4 Correct 565 ms 11000 KB Output is correct
5 Correct 381 ms 21496 KB Output is correct
6 Correct 353 ms 20092 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 768 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 179 ms 8184 KB Output is correct
9 Correct 224 ms 4216 KB Output is correct
10 Correct 565 ms 10876 KB Output is correct
11 Correct 384 ms 21464 KB Output is correct
12 Correct 360 ms 19960 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 179 ms 13944 KB Output is correct
15 Correct 36 ms 2040 KB Output is correct
16 Correct 569 ms 20728 KB Output is correct
17 Correct 382 ms 20152 KB Output is correct
18 Correct 365 ms 20088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 185 ms 8184 KB Output is correct
9 Correct 198 ms 4216 KB Output is correct
10 Correct 571 ms 10872 KB Output is correct
11 Correct 380 ms 21496 KB Output is correct
12 Correct 367 ms 19964 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 185 ms 13944 KB Output is correct
15 Correct 35 ms 2040 KB Output is correct
16 Correct 581 ms 20808 KB Output is correct
17 Correct 386 ms 20228 KB Output is correct
18 Correct 376 ms 20088 KB Output is correct
19 Correct 1238 ms 69748 KB Output is correct
20 Correct 1198 ms 67064 KB Output is correct
21 Correct 1217 ms 69496 KB Output is correct
22 Correct 1215 ms 67064 KB Output is correct
23 Correct 1204 ms 67012 KB Output is correct
24 Correct 1209 ms 67064 KB Output is correct
25 Correct 1215 ms 67208 KB Output is correct
26 Correct 1223 ms 69624 KB Output is correct
27 Correct 1223 ms 69708 KB Output is correct
28 Correct 1197 ms 67064 KB Output is correct
29 Correct 1214 ms 67192 KB Output is correct
30 Correct 1226 ms 67448 KB Output is correct