oj.uz

Submission #292085

# Submission time Handle Problem Language Result Execution time Memory
292085 2020-09-06T10:00:18 Z LifeHappen__ Wall (IOI14_wall) C++14
61 / 100
 1169 ms 83196 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){
   mn(mi[i],lzmi[i]);
   mn(ma[i],lzmi[i]);
   mx(mi[i],lzma[i]);
   mx(ma[i],lzma[i]);
   if(lzma[i]!=-inf || lzmi[i]!=inf){
      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);
   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);
      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);
   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 2 ms 384 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 8 ms 1408 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 175 ms 8196 KB Output is correct
3 Correct 322 ms 5724 KB Output is correct
4 Correct 1114 ms 16376 KB Output is correct
5 Correct 455 ms 16888 KB Output is correct
6 Correct 442 ms 16888 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 11 ms 1408 KB Output is correct
5 Correct 8 ms 1408 KB Output is correct
6 Correct 8 ms 1408 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 178 ms 8164 KB Output is correct
9 Correct 340 ms 5624 KB Output is correct
10 Correct 1113 ms 16504 KB Output is correct
11 Correct 449 ms 16888 KB Output is correct
12 Correct 439 ms 16888 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 182 ms 8184 KB Output is correct
15 Correct 52 ms 2808 KB Output is correct
16 Correct 1143 ms 16664 KB Output is correct
17 Correct 447 ms 16632 KB Output is correct
18 Correct 455 ms 16600 KB Output is correct

Subtask #4
0 / 39.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 2 ms 384 KB Output is correct
4 Correct 10 ms 1408 KB Output is correct
5 Correct 8 ms 1440 KB Output is correct
6 Correct 7 ms 1408 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 209 ms 8184 KB Output is correct
9 Correct 325 ms 5624 KB Output is correct
10 Correct 1112 ms 16384 KB Output is correct
11 Correct 440 ms 16888 KB Output is correct
12 Correct 445 ms 17016 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 178 ms 8184 KB Output is correct
15 Correct 52 ms 2808 KB Output is correct
16 Correct 1169 ms 16632 KB Output is correct
17 Correct 440 ms 16632 KB Output is correct
18 Correct 443 ms 16632 KB Output is correct
19 Runtime error 286 ms 83196 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -