oj.uz

Submission #292089

# Submission time Handle Problem Language Result Execution time Memory
292089 2020-09-06T10:01:58 Z LifeHappen__ Wall (IOI14_wall) C++14
100 / 100
 1491 ms 110328 KB 
#include <bits/stdc++.h>
#include "wall.h"

using namespace std;

#define forinc(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define fordec(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)
#define forb(a,b) for(int a=b._Find_first(); a<b.size(); a=b._Find_next(a))

#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define rall(a) rbegin(a),rend(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define gg exit(0);

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

typedef int64_t ll;
typedef unsigned long long ull;

const int N=2e6+5;
const int inf=1e9;
int n,k;
int ma[N*4], mi[N*4];
int lzma[N*4], lzmi[N*4];
int ret[N];

void build(int i,int l,int r){
   //ma[i]=inf, mi[i]=inf;
   lzma[i]=-inf;
   lzmi[i]=inf;
   if(l==r) return;
   int mid=l+(r-l)/2;
   build(i<<1,l,mid); build(i<<1|1,mid+1,r);
}

#define lc (i<<1)
#define rc (i<<1|1)

void mx(int &x,int y){x=max(x,y);}
void mn(int &x,int y){x=min(x,y);}

void trans(int i,int l,int r){
   mn(mi[i],lzmi[i]);
   mn(ma[i],lzmi[i]);
   mx(mi[i],lzma[i]);
   mx(ma[i],lzma[i]);
   if(l!=r){
      mx(ma[lc],lzma[i]); mn(ma[lc],lzmi[i]);
      mx(ma[rc],lzma[i]); mn(ma[rc],lzmi[i]);
      mx(lzma[lc],lzma[i]); mn(lzma[lc],lzmi[i]);
      mx(lzma[rc],lzma[i]); mn(lzma[rc],lzmi[i]);
      mx(lzmi[lc],lzma[i]); mn(lzmi[lc],lzmi[i]);
      mx(lzmi[rc],lzma[i]); mn(lzmi[rc],lzmi[i]);
      lzma[i]=-inf; lzmi[i]=inf;
   }
}

void upd(int i,int l,int r,int u,int v,int val,int o){
   trans(i,l,r);
   if(v<l || u>r) return;
   if(u<=l && r<=v){
      if(o==1){
         mx(lzma[i],val);
         mx(lzmi[i],val);
      } else{
         mn(lzma[i],val);
         mn(lzmi[i],val);
      }
      trans(i,l,r);
      return;
   }
   int mid=l+(r-l)/2;
   upd(lc,l,mid,u,v,val,o); upd(rc,mid+1,r,u,v,val,o);
   ma[i]=max(ma[lc],ma[rc]);
   mi[i]=min(mi[lc],mi[rc]);
}
void dfs(int i,int l,int r){
   trans(i,l,r);
   if(l==r){
      ret[l]=ma[i];
      return;
   }
   int mid=l+(r-l)/2;
   dfs(lc,l,mid); dfs(rc,mid+1,r);
}

void buildWall(int _n,int _k,int P[],int L[],int R[],int H[],int ans[]){
   n=_n, k=_k;
   build(1,1,n);
   forinc(i,0,k-1){
      upd(1,1,n,L[i]+1,R[i]+1,H[i],P[i]);
   }
   dfs(1,1,n);
   forinc(i,1,n) ans[i-1]=ret[i];
}
/*
int32_t main(){
   fasty;

   #define task "buildwall"
   if(fopen(task".inp","r")) freopen(task".inp","r",stdin);

   cin>>n>>k;
   forinc(i,0,k-1) cin>>p[i]>>x[i]>>y[i]>>h[i];
   //buildWall(n,k,p,x,y,h,ret);
   build(1,1,n);
   forinc(i,0,k-1){
      upd(1,1,n,x[i]+1,y[i]+1,h[i],p[i]);
   }
   dfs(1,1,n);
   forinc(i,1,n) cout<<ret[i]<<' ';
}
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 11 ms 1008 KB Output is correct
5 Correct 12 ms 1024 KB Output is correct
6 Correct 9 ms 1024 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 197 ms 8312 KB Output is correct
3 Correct 335 ms 4856 KB Output is correct
4 Correct 1030 ms 13252 KB Output is correct
5 Correct 559 ms 13800 KB Output is correct
6 Correct 540 ms 13944 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 9 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 172 ms 8184 KB Output is correct
9 Correct 332 ms 4868 KB Output is correct
10 Correct 1067 ms 13344 KB Output is correct
11 Correct 552 ms 13768 KB Output is correct
12 Correct 557 ms 13944 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 176 ms 8312 KB Output is correct
15 Correct 53 ms 2096 KB Output is correct
16 Correct 1084 ms 13688 KB Output is correct
17 Correct 556 ms 13560 KB Output is correct
18 Correct 560 ms 13560 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1152 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 204 ms 8184 KB Output is correct
9 Correct 327 ms 4984 KB Output is correct
10 Correct 1086 ms 13320 KB Output is correct
11 Correct 568 ms 13816 KB Output is correct
12 Correct 552 ms 13816 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 173 ms 8184 KB Output is correct
15 Correct 53 ms 2040 KB Output is correct
16 Correct 1090 ms 13688 KB Output is correct
17 Correct 550 ms 13560 KB Output is correct
18 Correct 563 ms 13560 KB Output is correct
19 Correct 1434 ms 99832 KB Output is correct
20 Correct 1421 ms 107900 KB Output is correct
21 Correct 1445 ms 110328 KB Output is correct
22 Correct 1425 ms 107788 KB Output is correct
23 Correct 1428 ms 107688 KB Output is correct
24 Correct 1421 ms 107752 KB Output is correct
25 Correct 1432 ms 108024 KB Output is correct
26 Correct 1440 ms 110204 KB Output is correct
27 Correct 1452 ms 110312 KB Output is correct
28 Correct 1491 ms 107768 KB Output is correct
29 Correct 1432 ms 107684 KB Output is correct
30 Correct 1477 ms 107684 KB Output is correct