oj.uz

Submission #289778

# Submission time Handle Problem Language Result Execution time Memory
289778 2020-09-03T04:02:26 Z tasfiq4 Wall (IOI14_wall) C++14
100 / 100
 1010 ms 73336 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
#define at1 (at*2)
#define at2 (at*2)+1
// add is true and remove is false
int A[5000000],B[5000000];
bool opt[5000000],mark[5000000];
int ans;
void change(int at,int h,bool w)
{
    if(w)
    {
        if(h>A[at] || (!opt[at] && B[at]<h))
        {
            opt[at]=w;
            A[at]=h;
            mark[at]=true;
        }
    }
    else
    {
        if(h<B[at] || (opt[at] && A[at]>h))
        {
            opt[at]=w;
            B[at]=h;
            mark[at]=true;
        }
    }
}
void propagate(int l,int r,int at)
{
    mark[at]=false;
    if(opt[at])
    {
        change(at1,B[at],false);
        change(at2,B[at],false);
        change(at1,A[at],true);
        change(at2,A[at],true);
    }
    else
    {
        change(at1,A[at],true);
        change(at2,A[at],true);
        change(at1,B[at],false);
        change(at2,B[at],false);
    }
    A[at]=0;B[at]=1e9+7;
}
void update(int l,int r,int at,int L,int R,int h,bool w)
{
    if(l>R || r<L) return;
    if(L<=l && r<=R)
    {
        change(at,h,w);
        return;
    }
    if(mark[at]) propagate(l,r,at);
    int mid=(l+r)/2;
    update(l,mid,at1,L,R,h,w);
    update(mid+1,r,at2,L,R,h,w);
}
void query(int l,int r,int at,int pos)
{
    if(l==r)
    {
        if(mark[at])
        {
            if(opt[at])
            {
                ans=min(B[at],ans);
                ans=max(A[at],ans);
            }
            else
            {
                ans=max(A[at],ans);
                ans=min(B[at],ans);
            }
        }
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) query(l,mid,at1,pos);
    else query(mid+1,r,at2,pos);
    if(mark[at])
    {
        if(opt[at])
            {
                ans=min(B[at],ans);
                ans=max(A[at],ans);
            }
            else
            {
                ans=max(A[at],ans);
                ans=min(B[at],ans);
            }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int i;
    fr(i,0,5000000) B[i]=1e9+7;
    fr(i,0,k)
    {
        update(1,n,1,left[i]+1,right[i]+1,height[i],(op[i]==1));
    }
    fr(i,1,n+1)
    {
        ans=0;
        query(1,n,1,i);
        finalHeight[i-1]=ans;
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19968 KB Output is correct
2 Correct 15 ms 20096 KB Output is correct
3 Correct 15 ms 19968 KB Output is correct
4 Correct 22 ms 20352 KB Output is correct
5 Correct 23 ms 20352 KB Output is correct
6 Correct 19 ms 20352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19968 KB Output is correct
2 Correct 188 ms 31480 KB Output is correct
3 Correct 262 ms 26744 KB Output is correct
4 Correct 759 ms 34552 KB Output is correct
5 Correct 348 ms 35832 KB Output is correct
6 Correct 327 ms 33912 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19968 KB Output is correct
2 Correct 14 ms 19992 KB Output is correct
3 Correct 14 ms 19968 KB Output is correct
4 Correct 22 ms 20352 KB Output is correct
5 Correct 19 ms 20352 KB Output is correct
6 Correct 18 ms 20352 KB Output is correct
7 Correct 12 ms 19968 KB Output is correct
8 Correct 181 ms 31608 KB Output is correct
9 Correct 263 ms 26744 KB Output is correct
10 Correct 756 ms 34552 KB Output is correct
11 Correct 351 ms 35832 KB Output is correct
12 Correct 323 ms 33912 KB Output is correct
13 Correct 12 ms 19968 KB Output is correct
14 Correct 188 ms 30840 KB Output is correct
15 Correct 61 ms 21496 KB Output is correct
16 Correct 901 ms 34456 KB Output is correct
17 Correct 336 ms 33912 KB Output is correct
18 Correct 342 ms 33916 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19968 KB Output is correct
2 Correct 13 ms 20068 KB Output is correct
3 Correct 14 ms 19968 KB Output is correct
4 Correct 21 ms 20352 KB Output is correct
5 Correct 18 ms 20352 KB Output is correct
6 Correct 18 ms 20352 KB Output is correct
7 Correct 12 ms 19968 KB Output is correct
8 Correct 187 ms 31608 KB Output is correct
9 Correct 263 ms 26744 KB Output is correct
10 Correct 750 ms 34552 KB Output is correct
11 Correct 341 ms 35704 KB Output is correct
12 Correct 328 ms 33912 KB Output is correct
13 Correct 13 ms 19968 KB Output is correct
14 Correct 188 ms 30712 KB Output is correct
15 Correct 60 ms 21496 KB Output is correct
16 Correct 911 ms 34568 KB Output is correct
17 Correct 343 ms 33976 KB Output is correct
18 Correct 340 ms 33912 KB Output is correct
19 Correct 997 ms 70392 KB Output is correct
20 Correct 996 ms 70520 KB Output is correct
21 Correct 1004 ms 73208 KB Output is correct
22 Correct 991 ms 70776 KB Output is correct
23 Correct 988 ms 70776 KB Output is correct
24 Correct 988 ms 70776 KB Output is correct
25 Correct 992 ms 70648 KB Output is correct
26 Correct 1008 ms 73208 KB Output is correct
27 Correct 1000 ms 73336 KB Output is correct
28 Correct 1008 ms 70648 KB Output is correct
29 Correct 1010 ms 70660 KB Output is correct
30 Correct 996 ms 70776 KB Output is correct