oj.uz

Submission #292084

# Submission time Handle Problem Language Result Execution time Memory
292084 2020-09-06T09:57:42 Z LifeHappen__ Wall (IOI14_wall) C++14
61 / 100
 1240 ms 156408 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 p[N],x[N],y[N],h[N],ret[N];
int ma[N*4], mi[N*4];
int lzma[N*4], lzmi[N*4];

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 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 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 187 ms 14072 KB Output is correct
3 Correct 338 ms 9464 KB Output is correct
4 Correct 1108 ms 25976 KB Output is correct
5 Correct 447 ms 27128 KB Output is correct
6 Correct 442 ms 25460 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 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 186 ms 13944 KB Output is correct
9 Correct 330 ms 9464 KB Output is correct
10 Correct 1106 ms 25976 KB Output is correct
11 Correct 457 ms 27128 KB Output is correct
12 Correct 438 ms 25592 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 202 ms 13944 KB Output is correct
15 Correct 53 ms 3448 KB Output is correct
16 Correct 1119 ms 26232 KB Output is correct
17 Correct 448 ms 25720 KB Output is correct
18 Correct 443 ms 25640 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 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 178 ms 13968 KB Output is correct
9 Correct 343 ms 9368 KB Output is correct
10 Correct 1126 ms 26104 KB Output is correct
11 Correct 461 ms 27000 KB Output is correct
12 Correct 439 ms 25464 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 179 ms 13952 KB Output is correct
15 Correct 53 ms 3448 KB Output is correct
16 Correct 1119 ms 26232 KB Output is correct
17 Correct 445 ms 25720 KB Output is correct
18 Correct 450 ms 25592 KB Output is correct
19 Incorrect 1240 ms 156408 KB Output isn't correct
20 Halted 0 ms 0 KB -