oj.uz

Submission #986859

# Submission time Handle Problem Language Result Execution time Memory
986859 2024-05-21T12:30:35 Z vjudge1 Wall (IOI14_wall) C++17
61 / 100
 353 ms 93268 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 << 20);
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 << 19;
    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 13 ms 33116 KB Output is correct
2 Correct 15 ms 33624 KB Output is correct
3 Correct 15 ms 33448 KB Output is correct
4 Correct 17 ms 33624 KB Output is correct
5 Correct 17 ms 33704 KB Output is correct
6 Correct 17 ms 33624 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33112 KB Output is correct
2 Correct 168 ms 56792 KB Output is correct
3 Correct 126 ms 49712 KB Output is correct
4 Correct 323 ms 76884 KB Output is correct
5 Correct 223 ms 74320 KB Output is correct
6 Correct 219 ms 71588 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 33116 KB Output is correct
2 Correct 15 ms 33628 KB Output is correct
3 Correct 15 ms 33372 KB Output is correct
4 Correct 17 ms 33628 KB Output is correct
5 Correct 17 ms 33628 KB Output is correct
6 Correct 17 ms 33628 KB Output is correct
7 Correct 13 ms 33112 KB Output is correct
8 Correct 182 ms 62664 KB Output is correct
9 Correct 113 ms 50512 KB Output is correct
10 Correct 353 ms 77128 KB Output is correct
11 Correct 223 ms 74112 KB Output is correct
12 Correct 225 ms 71760 KB Output is correct
13 Correct 13 ms 33116 KB Output is correct
14 Correct 173 ms 62632 KB Output is correct
15 Correct 32 ms 35924 KB Output is correct
16 Correct 346 ms 77396 KB Output is correct
17 Correct 222 ms 72024 KB Output is correct
18 Correct 219 ms 71196 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33112 KB Output is correct
2 Correct 16 ms 33628 KB Output is correct
3 Correct 15 ms 33372 KB Output is correct
4 Correct 18 ms 33624 KB Output is correct
5 Correct 17 ms 33624 KB Output is correct
6 Correct 17 ms 33824 KB Output is correct
7 Correct 13 ms 33220 KB Output is correct
8 Correct 167 ms 62632 KB Output is correct
9 Correct 117 ms 50364 KB Output is correct
10 Correct 334 ms 76880 KB Output is correct
11 Correct 224 ms 74360 KB Output is correct
12 Correct 217 ms 71760 KB Output is correct
13 Correct 13 ms 33116 KB Output is correct
14 Correct 168 ms 62628 KB Output is correct
15 Correct 31 ms 35932 KB Output is correct
16 Correct 340 ms 77256 KB Output is correct
17 Correct 226 ms 72020 KB Output is correct
18 Correct 225 ms 71460 KB Output is correct
19 Runtime error 161 ms 93268 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -