oj.uz

Submission #990234

# Submission time Handle Problem Language Result Execution time Memory
990234 2024-05-29T23:31:22 Z aaaaaarroz Wall (IOI14_wall) C++17
100 / 100
 341 ms 176716 KB 
#include "bits/stdc++.h"
#define F first
#define S second
#define ll long long
#define pii pair<int,int>
const int mxN = (1 << 22);
const int mod = 1e9 + 7;
const int inf = INT_MAX;
using namespace std;
struct event{
    int ty,op,id,val;
};
vector<event>q[mxN];
pii seg[mxN];
int N,s,e;
pii combine(pii a,pii b){
    pii c = a;
    c.F = min(c.F,b.S);
    c.F = max(c.F,b.F);
    c.S = min(a.S,b.S);
    return c;
}
void update(int ind,pii val){
    ind += N;
    seg[ind] = val;
    while(ind /= 2) seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    // N = exp2(ceil(log2(n)));
    N = 1 << 20;
    for(int i = 1;i < N * 2;i++){
        seg[i] = {0,inf};
    }
    for(int i = 0;i < k;i++){
        q[left[i]].push_back({1,op[i],i,height[i]});
        q[right[i] + 1].push_back({-1,op[i],i,height[i]});
    }
    for(int i = 0;i < n;i++){
        while(q[i].size()){
            auto u = q[i].back();
            q[i].pop_back();
            if(u.ty == -1){
                update(u.id,{0,inf});
            }else{
                if(u.op == 1) update(u.id,{u.val,inf});
                else update(u.id, {0,u.val});
            }
        }
        finalHeight[i] = seg[1].F;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 117076 KB Output is correct
2 Correct 28 ms 117576 KB Output is correct
3 Correct 28 ms 117340 KB Output is correct
4 Correct 30 ms 117584 KB Output is correct
5 Correct 33 ms 117596 KB Output is correct
6 Correct 29 ms 117596 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 117100 KB Output is correct
2 Correct 154 ms 143896 KB Output is correct
3 Correct 115 ms 132176 KB Output is correct
4 Correct 300 ms 156500 KB Output is correct
5 Correct 202 ms 153428 KB Output is correct
6 Correct 201 ms 151536 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 117092 KB Output is correct
2 Correct 26 ms 117592 KB Output is correct
3 Correct 27 ms 117340 KB Output is correct
4 Correct 29 ms 117592 KB Output is correct
5 Correct 29 ms 117584 KB Output is correct
6 Correct 27 ms 117588 KB Output is correct
7 Correct 26 ms 117084 KB Output is correct
8 Correct 156 ms 143784 KB Output is correct
9 Correct 114 ms 132692 KB Output is correct
10 Correct 282 ms 156308 KB Output is correct
11 Correct 208 ms 153428 KB Output is correct
12 Correct 200 ms 151640 KB Output is correct
13 Correct 26 ms 117092 KB Output is correct
14 Correct 151 ms 143776 KB Output is correct
15 Correct 44 ms 119896 KB Output is correct
16 Correct 285 ms 156552 KB Output is correct
17 Correct 203 ms 151636 KB Output is correct
18 Correct 207 ms 151056 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 117076 KB Output is correct
2 Correct 26 ms 117596 KB Output is correct
3 Correct 26 ms 117336 KB Output is correct
4 Correct 27 ms 117708 KB Output is correct
5 Correct 29 ms 117588 KB Output is correct
6 Correct 27 ms 117592 KB Output is correct
7 Correct 25 ms 117084 KB Output is correct
8 Correct 163 ms 144036 KB Output is correct
9 Correct 116 ms 132688 KB Output is correct
10 Correct 298 ms 156500 KB Output is correct
11 Correct 219 ms 153380 KB Output is correct
12 Correct 201 ms 151892 KB Output is correct
13 Correct 25 ms 117092 KB Output is correct
14 Correct 152 ms 143968 KB Output is correct
15 Correct 46 ms 119888 KB Output is correct
16 Correct 284 ms 156708 KB Output is correct
17 Correct 204 ms 151632 KB Output is correct
18 Correct 217 ms 150964 KB Output is correct
19 Correct 333 ms 176540 KB Output is correct
20 Correct 326 ms 173904 KB Output is correct
21 Correct 333 ms 176464 KB Output is correct
22 Correct 318 ms 173908 KB Output is correct
23 Correct 317 ms 174124 KB Output is correct
24 Correct 341 ms 174068 KB Output is correct
25 Correct 319 ms 173916 KB Output is correct
26 Correct 338 ms 176716 KB Output is correct
27 Correct 327 ms 176464 KB Output is correct
28 Correct 338 ms 173908 KB Output is correct
29 Correct 315 ms 173908 KB Output is correct
30 Correct 334 ms 174164 KB Output is correct