oj.uz

Submission #520785

# Submission time Handle Problem Language Result Execution time Memory
520785 2022-01-31T04:05:21 Z krit3379 Wall (IOI14_wall) C++17
100 / 100
 594 ms 75604 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 2000005

struct A{
    int mi,ma,exact;
};

A t[4*N];
int ll,rr,ma,mi;

void op(A &t,A add){
    auto [mi,ma,exact]=add;
    if(exact!=-1)t=add;
    else if(t.mi!=-1){
        if(t.exact==-1){
            t.ma=min(t.ma,ma);
            t.mi=max(t.mi,mi);
            if(t.mi>t.ma){
                if(t.mi==mi)t.exact=mi;
                else t.exact=ma;
            }
        }
        else{
            if(t.exact<mi)t.exact=mi;
            else if(t.exact>ma)t.exact=ma;
        }
    }
    else t=add;
}

void push(int x){
    if(t[x].mi!=-1){
        int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
        op(t[xl],t[x]);
        op(t[xr],t[x]);
        t[x].mi=-1;
    }
}

void cre(int x,int l,int r){
    if(l==r)return ;
    t[x]={-1,-1,-1};
    int mid=(l+r)/2;
    cre(x*2,l,mid);
    cre(x*2+1,mid+1,r);
}

void update(int x,int l,int r){
    if(r<ll||rr<l)return ;
    if(ll<=l&&r<=rr){
        op(t[x],{mi,ma,-1});
        return ;
    }
    push(x);
    int mid=(l+r)/2;
    update(x*2,l,mid);
    update(x*2+1,mid+1,r);
}

void sol(int x,int l,int r,int *ans){
    if(l==r){ans[l-1]=t[x].exact;return ;}
    push(x);
    int mid=(l+r)/2;
    sol(x*2,l,mid,ans);
    sol(x*2+1,mid+1,r,ans);
}

void buildWall(int n, int k, int *op, int *left, int *right, int *height, int *finalHeight){
    int i,h;
    cre(1,1,n);
    for(i=0;i<k;i++){
        ll=left[i]+1;
        rr=right[i]+1;
        h=height[i];
        if(op[i]==1)mi=h,ma=100000;
        else mi=0,ma=h;
        update(1,1,n);
    }
        sol(1,1,n,finalHeight);
}

Compilation message

wall.cpp: In function 'void push(int)':
wall.cpp:34:28: warning: unused variable 'mi' [-Wunused-variable]
   34 |         int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
      |                            ^~
wall.cpp:34:39: warning: unused variable 'ma' [-Wunused-variable]
   34 |         int xl=x*2,xr=xl+1,mi=t[x].mi,ma=t[x].ma;
      |                                       ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 5 ms 804 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 178 ms 8016 KB Output is correct
3 Correct 201 ms 4396 KB Output is correct
4 Correct 506 ms 11728 KB Output is correct
5 Correct 226 ms 12236 KB Output is correct
6 Correct 212 ms 12184 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 844 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 163 ms 8116 KB Output is correct
9 Correct 185 ms 4388 KB Output is correct
10 Correct 537 ms 11840 KB Output is correct
11 Correct 213 ms 12244 KB Output is correct
12 Correct 238 ms 12180 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 145 ms 8132 KB Output is correct
15 Correct 27 ms 1604 KB Output is correct
16 Correct 439 ms 11988 KB Output is correct
17 Correct 257 ms 11972 KB Output is correct
18 Correct 238 ms 11972 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 844 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 137 ms 8116 KB Output is correct
9 Correct 183 ms 4384 KB Output is correct
10 Correct 512 ms 11852 KB Output is correct
11 Correct 214 ms 12228 KB Output is correct
12 Correct 246 ms 12228 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 139 ms 8132 KB Output is correct
15 Correct 25 ms 1696 KB Output is correct
16 Correct 440 ms 12048 KB Output is correct
17 Correct 253 ms 12012 KB Output is correct
18 Correct 222 ms 12008 KB Output is correct
19 Correct 594 ms 75468 KB Output is correct
20 Correct 574 ms 73064 KB Output is correct
21 Correct 556 ms 75604 KB Output is correct
22 Correct 561 ms 72900 KB Output is correct
23 Correct 560 ms 72924 KB Output is correct
24 Correct 582 ms 72960 KB Output is correct
25 Correct 547 ms 72976 KB Output is correct
26 Correct 561 ms 75408 KB Output is correct
27 Correct 563 ms 75424 KB Output is correct
28 Correct 573 ms 72880 KB Output is correct
29 Correct 583 ms 73000 KB Output is correct
30 Correct 548 ms 72892 KB Output is correct