oj.uz

Submission #307274

# Submission time Handle Problem Language Result Execution time Memory
307274 2020-09-27T14:04:05 Z talant117408 Wall (IOI14_wall) C++17
100 / 100
 934 ms 88568 KB 
#include "wall.h"
#include <bits/stdc++.h> 

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 2e6+7;
vector <pii> lz(N*3);
vector <int> res(N);

void upd(int v, int mn, int mx){
    lz[v].first = min(max(lz[v].first, mn), mx);
    lz[v].second = min(max(lz[v].second, mn), mx);
}

void push(int v, int l, int r){
    if(l != r){
        upd(v<<1, lz[v].first, lz[v].second);
        upd((v<<1)+1, lz[v].first, lz[v].second);
    }
    lz[v] = {0, 2e9};
}

void update(int v, int l, int r, int ql, int qr, int op, int h){
    if(r < ql || l > qr) return;
    if(ql <= l && r <= qr){
        upd(v, (op==1?h:0), (op==2?h:2e9));
        return;
    }
    push(v, l, r); 
    int mid = (l+r)>>1;
    update(v<<1, l, mid, ql, qr, op, h);
    update((v<<1)+1, mid+1, r, ql, qr, op, h);
}

void build(int v, int l, int r){
    if(l == r){
        res[l] = lz[v].first;
        return;
    }
    push(v, l, r);
    int mid = (l+r) >> 1;
    build(v<<1, l, mid);
    build((v<<1)+1, mid+1, r);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0; i < k; i++){
        update(1, 0, n-1, left[i], right[i], op[i], height[i]);
    }
    build(1, 0, n-1);
    for(int i = 0; i < n; i++){
        finalHeight[i] = res[i];
    }
    
    return;
}
/*
int main(){
    int n, k, i, j, status = 0;
    status = scanf("%d%d", &n, &k);
    assert(status == 2);
    
    int* op = (int*)calloc(sizeof(int), k);
    int* left = (int*)calloc(sizeof(int), k);
    int* right = (int*)calloc(sizeof(int), k);
    int* height = (int*)calloc(sizeof(int), k);
    int* finalHeight = (int*)calloc(sizeof(int), n);
    
    for (i = 0; i < k; i++){
        status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
        assert(status == 4);
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    
    for (j = 0; j < n; j++)
        printf("%d\n", finalHeight[j]);

    return 0;
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 55160 KB Output is correct
2 Correct 39 ms 55168 KB Output is correct
3 Correct 37 ms 55160 KB Output is correct
4 Correct 43 ms 55416 KB Output is correct
5 Correct 42 ms 55416 KB Output is correct
6 Correct 43 ms 55544 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55168 KB Output is correct
2 Correct 208 ms 62968 KB Output is correct
3 Correct 253 ms 62328 KB Output is correct
4 Correct 641 ms 70904 KB Output is correct
5 Correct 416 ms 71288 KB Output is correct
6 Correct 396 ms 71476 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55160 KB Output is correct
2 Correct 38 ms 55160 KB Output is correct
3 Correct 38 ms 55160 KB Output is correct
4 Correct 46 ms 55416 KB Output is correct
5 Correct 43 ms 55416 KB Output is correct
6 Correct 42 ms 55416 KB Output is correct
7 Correct 36 ms 55160 KB Output is correct
8 Correct 211 ms 68728 KB Output is correct
9 Correct 254 ms 62456 KB Output is correct
10 Correct 654 ms 70776 KB Output is correct
11 Correct 415 ms 71368 KB Output is correct
12 Correct 402 ms 71416 KB Output is correct
13 Correct 37 ms 55164 KB Output is correct
14 Correct 211 ms 68728 KB Output is correct
15 Correct 70 ms 56312 KB Output is correct
16 Correct 641 ms 71160 KB Output is correct
17 Correct 417 ms 71160 KB Output is correct
18 Correct 402 ms 71160 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 55160 KB Output is correct
2 Correct 39 ms 55160 KB Output is correct
3 Correct 38 ms 55160 KB Output is correct
4 Correct 47 ms 55376 KB Output is correct
5 Correct 41 ms 55416 KB Output is correct
6 Correct 41 ms 55544 KB Output is correct
7 Correct 37 ms 55160 KB Output is correct
8 Correct 211 ms 68696 KB Output is correct
9 Correct 244 ms 62328 KB Output is correct
10 Correct 754 ms 71032 KB Output is correct
11 Correct 414 ms 71416 KB Output is correct
12 Correct 389 ms 71420 KB Output is correct
13 Correct 36 ms 55168 KB Output is correct
14 Correct 210 ms 68728 KB Output is correct
15 Correct 69 ms 56312 KB Output is correct
16 Correct 642 ms 71160 KB Output is correct
17 Correct 399 ms 71160 KB Output is correct
18 Correct 407 ms 71292 KB Output is correct
19 Correct 897 ms 88440 KB Output is correct
20 Correct 899 ms 86000 KB Output is correct
21 Correct 907 ms 88440 KB Output is correct
22 Correct 930 ms 86008 KB Output is correct
23 Correct 930 ms 85920 KB Output is correct
24 Correct 934 ms 86008 KB Output is correct
25 Correct 896 ms 85888 KB Output is correct
26 Correct 911 ms 88568 KB Output is correct
27 Correct 892 ms 88440 KB Output is correct
28 Correct 888 ms 86008 KB Output is correct
29 Correct 893 ms 86008 KB Output is correct
30 Correct 899 ms 86136 KB Output is correct