oj.uz

Submission #895960

# Submission time Handle Problem Language Result Execution time Memory
895960 2023-12-31T08:28:36 Z SalihSahin Wall (IOI14_wall) C++14
100 / 100
 698 ms 115540 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 1e9 + 7;
const int N = 3e5 + 5;
 
struct SEGT{
    vector<int> mx, mn, lazy;
 
    void init(int n){
        lazy.assign(4*n, -1);
        mx.assign(4*n, 0);
        mn.assign(4*n, 0);
    }
 
    void push(int ind){
        if(lazy[ind] == -1) return;
        mx[ind*2] = lazy[ind];
        mx[ind*2+1] = lazy[ind];
        mn[ind*2] = lazy[ind];
        mn[ind*2+1] = lazy[ind];
        lazy[ind*2] = lazy[ind];
        lazy[ind*2+1] = lazy[ind];
 
        lazy[ind] = -1;
    }
 
    void update1(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mx[ind] <= val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mn[ind] >= val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;
 
            update1(ind*2, l, m, ql, qr, val);
            update1(ind*2+1, m+1, r, ql, qr, val);
 
            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }
 
    void update2(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l >= ql && r <= qr && mn[ind] >= val){
            lazy[ind] = val;
            mx[ind] = val;
            mn[ind] = val;
        }
        else if(l >= ql && r <= qr && mx[ind] <= val) return;
        else if(l == r){
            mx[ind] = max(mx[ind], val);
            mn[ind] = mx[ind];
        }
        else{
            push(ind);
            int m = (l + r)/2;
 
            update2(ind*2, l, m, ql, qr, val);
            update2(ind*2+1, m+1, r, ql, qr, val);
 
            mx[ind] = max(mx[ind*2], mx[ind*2+1]);
            mn[ind] = min(mn[ind*2], mn[ind*2+1]);
        }
    }
 
    int query(int ind, int l, int r, int pos){
        if(l == r) return mx[ind];
        else{
            push(ind);
            int m = (l + r)/2;
 
            if(pos <= m) return query(ind*2, l, m, pos);
            else return query(ind*2+1, m+1, r, pos);
        }
    }
 
};
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   SEGT seg;
   seg.init(n);
   for(int i = 0; i < k; i++){
     if(op[i] == 1) seg.update1(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
     else seg.update2(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
   }
 
   for(int i = 0; i < n; i++){
     finalHeight[i] = seg.query(1, 1, n, i+1);
   }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 110 ms 8216 KB Output is correct
3 Correct 126 ms 4604 KB Output is correct
4 Correct 355 ms 13512 KB Output is correct
5 Correct 257 ms 13220 KB Output is correct
6 Correct 243 ms 17744 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 109 ms 8224 KB Output is correct
9 Correct 127 ms 4460 KB Output is correct
10 Correct 366 ms 13220 KB Output is correct
11 Correct 240 ms 13236 KB Output is correct
12 Correct 235 ms 17748 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 120 ms 11148 KB Output is correct
15 Correct 26 ms 2140 KB Output is correct
16 Correct 459 ms 18356 KB Output is correct
17 Correct 244 ms 18252 KB Output is correct
18 Correct 242 ms 18080 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 1056 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 107 ms 8016 KB Output is correct
9 Correct 137 ms 4456 KB Output is correct
10 Correct 353 ms 13224 KB Output is correct
11 Correct 236 ms 13224 KB Output is correct
12 Correct 245 ms 17864 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 174 ms 11312 KB Output is correct
15 Correct 26 ms 2140 KB Output is correct
16 Correct 453 ms 18516 KB Output is correct
17 Correct 235 ms 18084 KB Output is correct
18 Correct 240 ms 18180 KB Output is correct
19 Correct 680 ms 115264 KB Output is correct
20 Correct 698 ms 115300 KB Output is correct
21 Correct 676 ms 115276 KB Output is correct
22 Correct 665 ms 115540 KB Output is correct
23 Correct 683 ms 115244 KB Output is correct
24 Correct 668 ms 115264 KB Output is correct
25 Correct 684 ms 115280 KB Output is correct
26 Correct 674 ms 115260 KB Output is correct
27 Correct 692 ms 115212 KB Output is correct
28 Correct 663 ms 115156 KB Output is correct
29 Correct 687 ms 115284 KB Output is correct
30 Correct 674 ms 115284 KB Output is correct