oj.uz

Submission #871757

# Submission time Handle Problem Language Result Execution time Memory
871757 2023-11-11T12:42:24 Z HuyQuang_re_Zero Wall (IOI14_wall) C++14
100 / 100
 691 ms 104800 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "wall.h"
using namespace std;
const int m=100000;
int n,q,L[500001],R[500001],op[500001],H[500001],i,res[2000005];
struct Interval_Tree
{
    II st[8000005];
    void change(int id,II x)
    {
        if(x.fst>st[id].snd) st[id]={ x.fst,x.fst };
        else if(x.snd<st[id].fst) st[id]={ x.snd,x.snd };
        else st[id]={ max(st[id].fst,x.fst),min(st[id].snd,x.snd) };
    }
    void down(int id)
    {
        change(id*2,st[id]); change(id*2+1,st[id]);
        st[id]={ 0,m };
    }
    void build(int id,int l,int r)
    {
        if(l==r) { st[id]={ 0,0 }; return ; }
        int mid=(l+r)>>1;
        build(id*2,l,mid); build(id*2+1,mid+1,r);
        st[id]={ 0,m };
    }
    void update(int id,int l,int r,int u,int v,int x,int y)
    {
        if(u>r || v<l) return ;
        if(u<=l && r<=v) { change(id,{ x,y }); return ; }
        down(id);
        int mid=(l+r)>>1;
        update(id*2,l,mid,u,v,x,y); update(id*2+1,mid+1,r,u,v,x,y);
    }
    int get(int id,int l,int r,int u)
    {
        if(l==r) return st[id].fst;
        down(id);
        int mid=(l+r)>>1;
        if(u<=mid) return get(id*2,l,mid,u);
        return get(id*2+1,mid+1,r,u);
    }
} IT;
void buildWall(int n,int q,int op[],int L[],int R[],int H[],int res[])
{
    IT.build(1,1,n);
    for(i=0;i<q;i++)
    {
        L[i]++; R[i]++;
        if(op[i]==1) IT.update(1,1,n,L[i],R[i],H[i],m);
        else IT.update(1,1,n,L[i],R[i],0,H[i]);
    }
    for(i=0;i<n;i++) res[i]=IT.get(1,1,n,i+1);
}
/*
int main()
{
    freopen("wall.inp","r",stdin);
    freopen("wall.out","w",stdout);
    cin>>n>>q;
    for(i=0;i<q;i++) cin>>op[i]>>L[i]>>R[i]>>H[i];
    buildWall(n,q,op,L,R,H,res);
    for(i=0;i<n;i++) cout<<res[i]<<" ";
}
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 120 ms 16120 KB Output is correct
3 Correct 118 ms 11804 KB Output is correct
4 Correct 316 ms 24664 KB Output is correct
5 Correct 217 ms 25672 KB Output is correct
6 Correct 200 ms 24212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 4952 KB Output is correct
5 Correct 5 ms 4952 KB Output is correct
6 Correct 5 ms 4956 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 116 ms 15984 KB Output is correct
9 Correct 118 ms 12060 KB Output is correct
10 Correct 319 ms 24660 KB Output is correct
11 Correct 209 ms 25796 KB Output is correct
12 Correct 206 ms 24252 KB Output is correct
13 Correct 0 ms 2496 KB Output is correct
14 Correct 118 ms 15996 KB Output is correct
15 Correct 25 ms 5720 KB Output is correct
16 Correct 420 ms 25168 KB Output is correct
17 Correct 213 ms 24404 KB Output is correct
18 Correct 209 ms 24288 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 4920 KB Output is correct
5 Correct 5 ms 4956 KB Output is correct
6 Correct 5 ms 4952 KB Output is correct
7 Correct 1 ms 2492 KB Output is correct
8 Correct 114 ms 16060 KB Output is correct
9 Correct 114 ms 11860 KB Output is correct
10 Correct 330 ms 24660 KB Output is correct
11 Correct 212 ms 25680 KB Output is correct
12 Correct 216 ms 24304 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 117 ms 15956 KB Output is correct
15 Correct 24 ms 5768 KB Output is correct
16 Correct 425 ms 25168 KB Output is correct
17 Correct 212 ms 24404 KB Output is correct
18 Correct 211 ms 24408 KB Output is correct
19 Correct 657 ms 104492 KB Output is correct
20 Correct 647 ms 102224 KB Output is correct
21 Correct 651 ms 104736 KB Output is correct
22 Correct 658 ms 102228 KB Output is correct
23 Correct 650 ms 102212 KB Output is correct
24 Correct 652 ms 102308 KB Output is correct
25 Correct 658 ms 102304 KB Output is correct
26 Correct 659 ms 104532 KB Output is correct
27 Correct 691 ms 104800 KB Output is correct
28 Correct 647 ms 102056 KB Output is correct
29 Correct 656 ms 102228 KB Output is correct
30 Correct 675 ms 102228 KB Output is correct