oj.uz

Submission #795821

# Submission time Handle Problem Language Result Execution time Memory
795821 2023-07-27T16:28:02 Z idiotcomputer Wall (IOI14_wall) C++11
100 / 100
 520 ms 59652 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int MAX_N = 2000000;
const int NINF = 0;
const int INF = (1<<30);

struct node {
    int first = INF;
    int second = NINF;
};

pair<int,int> segt[4*MAX_N+1];

void app(int idx, pair<int,int> a){
    segt[idx].second = min(max(segt[idx].second,a.second), a.first);
    segt[idx].first = min(max(segt[idx].first,a.second),a.first);
    return;
}
void upd(int l, int r, int idx, int tl, int tr, int w, int h){
    if (l > tr || r < tl){
        return;
    }
    if (l >= tl && r <= tr){
        //mini
        if (w == 1){
            segt[idx].first = min(segt[idx].first,h);
            segt[idx].second = min(segt[idx].second,h);
        } else {
            segt[idx].first = max(segt[idx].first,h);
            segt[idx].second = max(segt[idx].second,h);
        }
        return;
    }
    int m = (l+r)/2;
    app(2*idx+1,segt[idx]);
    app(2*idx+2,segt[idx]);
    segt[idx].first = INF;
    segt[idx].second = NINF;
    
    upd(l,m,2*idx+1,tl,tr,w,h);
    upd(m+1,r,2*idx+2,tl,tr,w,h);
    return;
}

void solve(int l, int r, int idx, int finalHeight[]){
    if (l == r){
        //cout << l << ": " << segt[idx].first << ", " << segt[idx].second << '\n';
        if (segt[idx].first == INF && segt[idx].second == NINF){
            finalHeight[l] = 0;
        } else {
            finalHeight[l] = min(segt[idx].first,segt[idx].second);    
        }
        return;
    }
    int m = (l+r)/2;
    app(2*idx+1,segt[idx]);
    app(2*idx+2,segt[idx]);
    segt[idx].first = INF;
    segt[idx].second = NINF;
    solve(l,m,2*idx+1,finalHeight);
    solve(m+1,r,2*idx+2,finalHeight);
    return;
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i =0; i < k; i++){
        upd(0,n-1,0,left[i],right[i],op[i]-1,height[i]);
    }
    solve(0,n-1,0,finalHeight);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 101 ms 8100 KB Output is correct
3 Correct 118 ms 4172 KB Output is correct
4 Correct 327 ms 10700 KB Output is correct
5 Correct 220 ms 11772 KB Output is correct
6 Correct 217 ms 11708 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 672 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 102 ms 8056 KB Output is correct
9 Correct 115 ms 4184 KB Output is correct
10 Correct 319 ms 10676 KB Output is correct
11 Correct 227 ms 11796 KB Output is correct
12 Correct 219 ms 11740 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 103 ms 8308 KB Output is correct
15 Correct 21 ms 1724 KB Output is correct
16 Correct 322 ms 11484 KB Output is correct
17 Correct 222 ms 11440 KB Output is correct
18 Correct 223 ms 11680 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 100 ms 8140 KB Output is correct
9 Correct 114 ms 4124 KB Output is correct
10 Correct 319 ms 10744 KB Output is correct
11 Correct 233 ms 11708 KB Output is correct
12 Correct 225 ms 11724 KB Output is correct
13 Correct 0 ms 308 KB Output is correct
14 Correct 106 ms 8332 KB Output is correct
15 Correct 20 ms 1620 KB Output is correct
16 Correct 323 ms 11484 KB Output is correct
17 Correct 219 ms 11532 KB Output is correct
18 Correct 220 ms 11484 KB Output is correct
19 Correct 520 ms 59528 KB Output is correct
20 Correct 507 ms 57052 KB Output is correct
21 Correct 516 ms 59652 KB Output is correct
22 Correct 516 ms 57056 KB Output is correct
23 Correct 519 ms 57096 KB Output is correct
24 Correct 513 ms 57064 KB Output is correct
25 Correct 510 ms 57080 KB Output is correct
26 Correct 516 ms 59524 KB Output is correct
27 Correct 517 ms 59592 KB Output is correct
28 Correct 507 ms 57012 KB Output is correct
29 Correct 507 ms 57088 KB Output is correct
30 Correct 519 ms 57088 KB Output is correct