oj.uz

Submission #986860

# Submission time Handle Problem Language Result Execution time Memory
986860 2024-05-21T12:31:32 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 465 ms 181584 KB 
#pragma once
#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;
    }
}

Compilation message

wall.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117076 KB Output is correct
2 Correct 52 ms 117504 KB Output is correct
3 Correct 52 ms 117332 KB Output is correct
4 Correct 56 ms 117584 KB Output is correct
5 Correct 58 ms 117584 KB Output is correct
6 Correct 54 ms 117584 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 117332 KB Output is correct
2 Correct 204 ms 140696 KB Output is correct
3 Correct 150 ms 130644 KB Output is correct
4 Correct 369 ms 151412 KB Output is correct
5 Correct 262 ms 148048 KB Output is correct
6 Correct 258 ms 147280 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 117084 KB Output is correct
2 Correct 52 ms 117500 KB Output is correct
3 Correct 52 ms 117328 KB Output is correct
4 Correct 54 ms 117584 KB Output is correct
5 Correct 53 ms 117588 KB Output is correct
6 Correct 61 ms 117604 KB Output is correct
7 Correct 51 ms 117204 KB Output is correct
8 Correct 202 ms 140756 KB Output is correct
9 Correct 156 ms 130548 KB Output is correct
10 Correct 418 ms 151340 KB Output is correct
11 Correct 263 ms 148412 KB Output is correct
12 Correct 286 ms 147040 KB Output is correct
13 Correct 50 ms 117072 KB Output is correct
14 Correct 204 ms 140716 KB Output is correct
15 Correct 69 ms 119380 KB Output is correct
16 Correct 357 ms 151428 KB Output is correct
17 Correct 264 ms 146868 KB Output is correct
18 Correct 263 ms 146160 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 117084 KB Output is correct
2 Correct 53 ms 117504 KB Output is correct
3 Correct 52 ms 117328 KB Output is correct
4 Correct 55 ms 117648 KB Output is correct
5 Correct 57 ms 117464 KB Output is correct
6 Correct 54 ms 117604 KB Output is correct
7 Correct 50 ms 117076 KB Output is correct
8 Correct 207 ms 141248 KB Output is correct
9 Correct 151 ms 130780 KB Output is correct
10 Correct 465 ms 151672 KB Output is correct
11 Correct 262 ms 148152 KB Output is correct
12 Correct 285 ms 147028 KB Output is correct
13 Correct 54 ms 117076 KB Output is correct
14 Correct 211 ms 140936 KB Output is correct
15 Correct 74 ms 119380 KB Output is correct
16 Correct 389 ms 151664 KB Output is correct
17 Correct 260 ms 146876 KB Output is correct
18 Correct 265 ms 146236 KB Output is correct
19 Correct 434 ms 171072 KB Output is correct
20 Correct 432 ms 179112 KB Output is correct
21 Correct 435 ms 181564 KB Output is correct
22 Correct 427 ms 179032 KB Output is correct
23 Correct 456 ms 179064 KB Output is correct
24 Correct 426 ms 179140 KB Output is correct
25 Correct 438 ms 179016 KB Output is correct
26 Correct 438 ms 181528 KB Output is correct
27 Correct 430 ms 181584 KB Output is correct
28 Correct 432 ms 178956 KB Output is correct
29 Correct 436 ms 179156 KB Output is correct
30 Correct 425 ms 179236 KB Output is correct