oj.uz

Submission #338568

# Submission time Handle Problem Language Result Execution time Memory
338568 2020-12-23T12:25:02 Z Sho10 Wall (IOI14_wall) C++14
100 / 100
 1077 ms 69688 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#include "wall.h"
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define PI 3.14159265359
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
pair<int,int>tree[8000010];
void build(int node,int l,int r){
if(l==r){
    tree[node]=mp(-1,-1);
    return;
}
ll mid=(l+r)>>1ll;
build(2*node,l,mid);
build(2*node+1,mid+1,r);
}
void add(pair<int,int> &s,pair<int,int> &j){
if(s==mp(-1,-1)){
    return;
}
if(j==mp(-1,-1)){
    j=s;
    s=mp(-1,-1);
    return;
}
int hs=s.f,rs=s.s,hj=j.f,rj=j.s;
if(rs<hj){
j={max(rs,hs),min(rs,rj)};
}else{
j={max(hj,hs),min(rs,rj)};
    }
    s=mp(-1,-1);
return;
}
void update(int node,int l,int r,int st,int dr,int type,int h){
if(st>dr){
    return;
}
if(l==st&&r==dr){
        pair<int,int>p={0,0};
    if(type==1){
      p.f=h;
      p.s=100000;
    }else {
    p.s=h;
    }
    add(p,tree[node]);
    return;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
int mid=(l+r)>>1ll;
update(2*node,l,mid,st,min(dr,mid),type,h);
update(2*node+1,mid+1,r,max(st,mid+1),dr,type,h);
return;
}
int query(int node,int l,int r,int pos){
if(l==r){
    return tree[node].f;
}
pair<int,int>p=tree[node];
add(tree[node],tree[node*2]);
add(p,tree[node*2+1]);
int mid=(l+r)>>1ll;
if(pos<=mid){
return query(2*node,l,mid,pos);
}else return query(2*node+1,mid+1,r,pos);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
build(1,1,n);
for(int i=0;i<k;i++)
{
    update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
}
for(int i=0;i<n;i++)
{
    finalHeight[i]=query(1,1,n,i+1);
}
return;
}
/*
int32_t main(){
CODE_START;
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 7 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 159 ms 8300 KB Output is correct
3 Correct 230 ms 4204 KB Output is correct
4 Correct 671 ms 20460 KB Output is correct
5 Correct 353 ms 21516 KB Output is correct
6 Correct 358 ms 19948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 9 ms 876 KB Output is correct
5 Correct 6 ms 876 KB Output is correct
6 Correct 6 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 159 ms 14124 KB Output is correct
9 Correct 228 ms 8044 KB Output is correct
10 Correct 670 ms 20380 KB Output is correct
11 Correct 359 ms 21644 KB Output is correct
12 Correct 345 ms 19948 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 164 ms 13980 KB Output is correct
15 Correct 39 ms 2028 KB Output is correct
16 Correct 696 ms 20716 KB Output is correct
17 Correct 352 ms 20076 KB Output is correct
18 Correct 364 ms 20076 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 8 ms 876 KB Output is correct
5 Correct 8 ms 876 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 161 ms 13932 KB Output is correct
9 Correct 231 ms 8044 KB Output is correct
10 Correct 686 ms 20460 KB Output is correct
11 Correct 354 ms 21496 KB Output is correct
12 Correct 343 ms 19948 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 166 ms 14028 KB Output is correct
15 Correct 40 ms 2028 KB Output is correct
16 Correct 764 ms 20644 KB Output is correct
17 Correct 359 ms 20076 KB Output is correct
18 Correct 357 ms 20076 KB Output is correct
19 Correct 1045 ms 69604 KB Output is correct
20 Correct 1020 ms 67180 KB Output is correct
21 Correct 1046 ms 69484 KB Output is correct
22 Correct 1077 ms 67180 KB Output is correct
23 Correct 1025 ms 67008 KB Output is correct
24 Correct 1028 ms 67096 KB Output is correct
25 Correct 1024 ms 67240 KB Output is correct
26 Correct 1020 ms 69608 KB Output is correct
27 Correct 1037 ms 69688 KB Output is correct
28 Correct 1025 ms 67052 KB Output is correct
29 Correct 1043 ms 67052 KB Output is correct
30 Correct 1022 ms 67052 KB Output is correct