oj.uz

Submission #1113287

# Submission time Handle Problem Language Result Execution time Memory
1113287 2024-11-16T09:45:02 Z kiethm07 Wall (IOI14_wall) C++11
100 / 100
 1430 ms 82676 KB 
#include <bits/stdc++.h>
#include <wall.h>

#define pii pair<int,int>
#define pli pair<long long,pii>
#define fi first
#define se second

#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end()

using namespace std;

typedef long long ll;
typedef long double ld;

const int inf = 1e9;
const ll linf = 1e16;
const double pi = acos(-1);

class IT{
private:
    vector<int> low, high;
public:
    IT (int n){
        low.resize(4 * n,0);
        high.resize(4 * n,inf);
    }
    void apply(int id,int x,int y){
        high[id] = min(high[id], y);
        high[id] = max(high[id], x);
        low[id] = max(low[id], x);
        low[id] = min(low[id], y);
    }
    void down(int id,int l,int r){
        if (l == r) return;
        apply(id * 2,low[id],high[id]);
        apply(id * 2 + 1,low[id],high[id]);
        low[id] = 0;
        high[id] = inf;
    }
    void update(int id,int l,int r,int u,int v,int f,int g){
        down(id,l,r);
        if (l > v || r < u) return;
        if (l >= u && r <= v){
            apply(id,f,g);
            down(id,l,r);
            return;
        }
        int mid = (l + r) / 2;
        update(id * 2,l,mid,u,v,f,g);
        update(id * 2 + 1,mid + 1,r,u,v,f,g);
//            cout << l << " " << r << " " << u << " " << v << " " << low[id] << " " << high[id] << "\n";

    }
    int query(int id,int l,int r,int i){
        down(id,l,r);
//        cout << l << " " << r << " " << low[id] << " " << high[id] << "\n";
        if (l > i || r < i) return -1;
        if (l == r){
            return low[id];
        }
        int mid = (l + r) / 2;
        int q1 = query(id * 2,l,mid,i);
        int q2 = query(id * 2 + 1,mid + 1,r,i);
        if (q1 == -1) return q2;
        return q1;
    }
};

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    IT t(n);
    for (int i = 0; i < k; i++){
        int l = left[i] + 1;
        int r = right[i] + 1;
//        cout << l << " " << r << " " << op[i] << " " << height[i] << "\n";
        if (op[i] == 1) t.update(1,1,n,l,r,height[i],inf);
        if (op[i] == 2) t.update(1,1,n,l,r,0,height[i]);
    }
    for (int i = 1; i <= n; i++){
        finalHeight[i - 1] = t.query(1,1,n,i);
//        cout << finalHeight[i - 1] << " ";
    }
}
//
//int main(){
//    #define TEXT "a"
//    cin.tie(0) -> sync_with_stdio(0);
//    if (fopen(TEXT".inp","r")){
//        freopen(TEXT".inp","r",stdin);
//        freopen(TEXT".out","w",stdout);
//    }
//    int n = 10, k = 6;
//    int op[k] = {1,2,2,1,1,2};
//    int left[k] = {1,4,3,0,2,6};
//    int right[k] = {8,9,6,5,2,7};
//    int height[k] = {4,1,5,3,5,0};
//    int finalHeight[n] = {};
//    buildWall(n,k,op,left,right,height,finalHeight);
//    return 0;
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 7 ms 848 KB Output is correct
5 Correct 7 ms 1016 KB Output is correct
6 Correct 7 ms 848 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 95 ms 11368 KB Output is correct
3 Correct 149 ms 4116 KB Output is correct
4 Correct 460 ms 16784 KB Output is correct
5 Correct 305 ms 17032 KB Output is correct
6 Correct 264 ms 16268 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 804 KB Output is correct
5 Correct 7 ms 848 KB Output is correct
6 Correct 8 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 96 ms 11308 KB Output is correct
9 Correct 179 ms 6132 KB Output is correct
10 Correct 468 ms 16788 KB Output is correct
11 Correct 283 ms 16968 KB Output is correct
12 Correct 253 ms 11592 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 88 ms 11440 KB Output is correct
15 Correct 34 ms 1872 KB Output is correct
16 Correct 433 ms 11592 KB Output is correct
17 Correct 261 ms 16400 KB Output is correct
18 Correct 255 ms 11776 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 6 ms 848 KB Output is correct
5 Correct 10 ms 848 KB Output is correct
6 Correct 6 ms 848 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 124 ms 11168 KB Output is correct
9 Correct 156 ms 4168 KB Output is correct
10 Correct 518 ms 11600 KB Output is correct
11 Correct 285 ms 17040 KB Output is correct
12 Correct 290 ms 15460 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 104 ms 11336 KB Output is correct
15 Correct 27 ms 1360 KB Output is correct
16 Correct 471 ms 14920 KB Output is correct
17 Correct 290 ms 16712 KB Output is correct
18 Correct 259 ms 11728 KB Output is correct
19 Correct 1289 ms 79092 KB Output is correct
20 Correct 1303 ms 78584 KB Output is correct
21 Correct 1315 ms 78576 KB Output is correct
22 Correct 1371 ms 78584 KB Output is correct
23 Correct 1430 ms 78664 KB Output is correct
24 Correct 1344 ms 78588 KB Output is correct
25 Correct 1275 ms 78664 KB Output is correct
26 Correct 1279 ms 82676 KB Output is correct
27 Correct 1305 ms 78580 KB Output is correct
28 Correct 1255 ms 78592 KB Output is correct
29 Correct 1344 ms 78536 KB Output is correct
30 Correct 1266 ms 78664 KB Output is correct