oj.uz

Submission #31158

# Submission time Handle Problem Language Result Execution time Memory
31158 2017-08-12T05:15:33 Z pasa3232 Wall (IOI14_wall) C++14
100 / 100
 1299 ms 95788 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int INF=1987654321;

struct A{
    int st, en;
    A operator+(const A &r){
        int x=max(r.st, st), y=min(r.en, en);
        if(x<=y) return (A){x, y};
        else if(x==r.st) return (A){x, x};
        else return (A){y, y};
    }
}tree[10000010];
int n, m;

void make_tree(int node, int s, int e){
    if(s==e){
        tree[node]=(A){0, INF};
        return;
    }
    int m=s+e>>1;
    make_tree(node*2, s, m);
    make_tree(node*2+1, m+1, e);
    tree[node]=tree[node*2]+tree[node*2+1];
}

void update(int node, int s, int e, int s1, int e1, A val){
    if(s>e1||e<s1) return;
    if(s1<=s&&e<=e1){
        tree[node]=tree[node]+val;
        return;
    }
    if(tree[node].st!=0||tree[node].en!=INF){
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]=(A){0, INF};
    }
    int m=s+e>>1;
    update(node*2, s, m, s1, e1, val);
    update(node*2+1, m+1, e, s1, e1, val);
}

A get(int node, int s, int e, int pos){
    if(s>pos||e<pos) return (A){0, INF};
    if(s==e){
        return tree[node];
    }
    if(tree[node].st!=0||tree[node].en!=INF){
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]=(A){0, INF};
    }
    int m=s+e>>1;
    return get(node*2, s, m, pos)+get(node*2+1, m+1, e, pos);
}

void buildWall(int N, int M, int op[], int left[], int right[], int height[], int finalHeight[]){
    n=N, m=M;
    make_tree(1, 0, n-1);
    for(int i=0; i<m; i++){
        int type=op[i], s=left[i], e=right[i], x=height[i];
        if(type==1){
            A rev=(A){x, INF};
            update(1, 0, n-1, s, e, rev);
        }
        else{
            A rev=(A){0, x};
            update(1, 0, n-1, s, e, rev);
        }
    }
    for(int i=0; i<n; i++) finalHeight[i]=get(1, 0, n-1, i).st;
}

Compilation message

wall.cpp: In function 'void make_tree(int, int, int)':
wall.cpp:22:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^
wall.cpp: In function 'void update(int, int, int, int, int, A)':
wall.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^
wall.cpp: In function 'A get(int, int, int, int)':
wall.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 80148 KB Output is correct
2 Correct 0 ms 80284 KB Output is correct
3 Correct 0 ms 80148 KB Output is correct
4 Correct 6 ms 80284 KB Output is correct
5 Correct 6 ms 80284 KB Output is correct
6 Correct 3 ms 80284 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 80148 KB Output is correct
2 Correct 146 ms 87972 KB Output is correct
3 Correct 219 ms 83544 KB Output is correct
4 Correct 759 ms 88364 KB Output is correct
5 Correct 386 ms 88364 KB Output is correct
6 Correct 366 ms 88364 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 80148 KB Output is correct
2 Correct 0 ms 80284 KB Output is correct
3 Correct 3 ms 80148 KB Output is correct
4 Correct 13 ms 80284 KB Output is correct
5 Correct 6 ms 80284 KB Output is correct
6 Correct 9 ms 80284 KB Output is correct
7 Correct 0 ms 80148 KB Output is correct
8 Correct 186 ms 87972 KB Output is correct
9 Correct 229 ms 83544 KB Output is correct
10 Correct 619 ms 88364 KB Output is correct
11 Correct 253 ms 88364 KB Output is correct
12 Correct 339 ms 88364 KB Output is correct
13 Correct 0 ms 80148 KB Output is correct
14 Correct 199 ms 87972 KB Output is correct
15 Correct 53 ms 80776 KB Output is correct
16 Correct 739 ms 88364 KB Output is correct
17 Correct 343 ms 88364 KB Output is correct
18 Correct 366 ms 88364 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 80148 KB Output is correct
2 Correct 0 ms 80284 KB Output is correct
3 Correct 0 ms 80148 KB Output is correct
4 Correct 6 ms 80284 KB Output is correct
5 Correct 6 ms 80284 KB Output is correct
6 Correct 6 ms 80284 KB Output is correct
7 Correct 0 ms 80148 KB Output is correct
8 Correct 206 ms 87972 KB Output is correct
9 Correct 296 ms 83544 KB Output is correct
10 Correct 753 ms 88364 KB Output is correct
11 Correct 303 ms 88364 KB Output is correct
12 Correct 329 ms 88364 KB Output is correct
13 Correct 0 ms 80148 KB Output is correct
14 Correct 193 ms 87972 KB Output is correct
15 Correct 43 ms 80776 KB Output is correct
16 Correct 879 ms 88364 KB Output is correct
17 Correct 353 ms 88364 KB Output is correct
18 Correct 299 ms 88364 KB Output is correct
19 Correct 1136 ms 95788 KB Output is correct
20 Correct 1246 ms 95788 KB Output is correct
21 Correct 1156 ms 95788 KB Output is correct
22 Correct 1176 ms 95788 KB Output is correct
23 Correct 1233 ms 95788 KB Output is correct
24 Correct 1093 ms 95788 KB Output is correct
25 Correct 1219 ms 95788 KB Output is correct
26 Correct 1259 ms 95788 KB Output is correct
27 Correct 1213 ms 95788 KB Output is correct
28 Correct 1299 ms 95788 KB Output is correct
29 Correct 1039 ms 95788 KB Output is correct
30 Correct 1026 ms 95788 KB Output is correct