oj.uz

Submission #68620

# Submission time Handle Problem Language Result Execution time Memory
68620 2018-08-17T14:54:46 Z Vahan Wall (IOI14_wall) C++17
100 / 100
 1326 ms 186700 KB 
#include "wall.h"
#include<algorithm>
using namespace std;
pair<int,int> t[17000000];
void update(int l,int r,int L,int R,int v,int a,int b)
{
    if(l>r)
        return;
    if(l==L && r==R)
    {
        if(b==1)
        {
            t[v].first=max(a,t[v].first);
            t[v].second=max(a,t[v].second);
        }
        if(b==2)
        {
            t[v].first=min(a,t[v].first);
            t[v].second=min(a,t[v].second);
        }
    }
    else
    {
        t[2*v].first=min(max(t[2*v].first,t[v].first),t[v].second);
        t[2*v].second=min(max(t[2*v].second,t[v].first),t[v].second);
        t[2*v+1].first=min(max(t[2*v+1].first,t[v].first),t[v].second);
        t[2*v+1].second=min(max(t[2*v+1].second,t[v].first),t[v].second);
        t[v].first=0;
        t[v].second=1e5+10;
        int mid=(L+R)/2;
        update(l,min(mid,r),L,mid,2*v,a,b);
        update(max(l,mid+1),r,mid+1,R,2*v+1,a,b);
    }
}
int get(int l,int r,int v,int a)
{
    if(l==r)
        return t[v].first;
    t[2*v].first=min(max(t[2*v].first,t[v].first),t[v].second);
    t[2*v].second=min(max(t[2*v].second,t[v].first),t[v].second);
    t[2*v+1].first=min(max(t[2*v+1].first,t[v].first),t[v].second);
    t[2*v+1].second=min(max(t[2*v+1].second,t[v].first),t[v].second);
    t[v].first=0;
    t[v].second=1e5+10;
    int mid=(l+r)/2;
    if(a<=mid)
        get(l,mid,2*v,a);
    else
        get(mid+1,r,2*v+1,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for(int i=0;i<k;i++)
        update(left[i],right[i],0,n-1,1,height[i],op[i]);
    for(int i=0;i<n;i++)
        finalHeight[i]=get(0,n-1,1,i);
    return;
}

Compilation message

wall.cpp: In function 'int get(int, int, int, int)':
wall.cpp:50:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 5 ms 648 KB Output is correct
3 Correct 5 ms 648 KB Output is correct
4 Correct 10 ms 1068 KB Output is correct
5 Correct 10 ms 1192 KB Output is correct
6 Correct 14 ms 1192 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1192 KB Output is correct
2 Correct 203 ms 14664 KB Output is correct
3 Correct 264 ms 14664 KB Output is correct
4 Correct 616 ms 20164 KB Output is correct
5 Correct 521 ms 20632 KB Output is correct
6 Correct 346 ms 28184 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 28184 KB Output is correct
2 Correct 4 ms 28184 KB Output is correct
3 Correct 5 ms 28184 KB Output is correct
4 Correct 11 ms 28184 KB Output is correct
5 Correct 12 ms 28184 KB Output is correct
6 Correct 12 ms 28184 KB Output is correct
7 Correct 2 ms 28184 KB Output is correct
8 Correct 201 ms 31300 KB Output is correct
9 Correct 244 ms 31312 KB Output is correct
10 Correct 726 ms 47552 KB Output is correct
11 Correct 505 ms 58056 KB Output is correct
12 Correct 393 ms 66668 KB Output is correct
13 Correct 3 ms 66668 KB Output is correct
14 Correct 207 ms 69304 KB Output is correct
15 Correct 40 ms 69304 KB Output is correct
16 Correct 782 ms 82464 KB Output is correct
17 Correct 429 ms 91492 KB Output is correct
18 Correct 397 ms 100484 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 100484 KB Output is correct
2 Correct 5 ms 100484 KB Output is correct
3 Correct 4 ms 100484 KB Output is correct
4 Correct 13 ms 100484 KB Output is correct
5 Correct 10 ms 100484 KB Output is correct
6 Correct 11 ms 100484 KB Output is correct
7 Correct 3 ms 100484 KB Output is correct
8 Correct 205 ms 103768 KB Output is correct
9 Correct 210 ms 103768 KB Output is correct
10 Correct 643 ms 119748 KB Output is correct
11 Correct 433 ms 130384 KB Output is correct
12 Correct 415 ms 130424 KB Output is correct
13 Correct 3 ms 130424 KB Output is correct
14 Correct 261 ms 130424 KB Output is correct
15 Correct 45 ms 130424 KB Output is correct
16 Correct 668 ms 130424 KB Output is correct
17 Correct 363 ms 130424 KB Output is correct
18 Correct 354 ms 130424 KB Output is correct
19 Correct 1155 ms 177976 KB Output is correct
20 Correct 1218 ms 177976 KB Output is correct
21 Correct 1310 ms 178164 KB Output is correct
22 Correct 1255 ms 184296 KB Output is correct
23 Correct 1300 ms 184296 KB Output is correct
24 Correct 1293 ms 184296 KB Output is correct
25 Correct 1326 ms 184296 KB Output is correct
26 Correct 1127 ms 186700 KB Output is correct
27 Correct 1185 ms 186700 KB Output is correct
28 Correct 1253 ms 186700 KB Output is correct
29 Correct 1096 ms 186700 KB Output is correct
30 Correct 1275 ms 186700 KB Output is correct