oj.uz

Submission #930785

# Submission time Handle Problem Language Result Execution time Memory
930785 2024-02-20T12:16:18 Z vjudge1 Wall (IOI14_wall) C++17
100 / 100
 1014 ms 98384 KB 
#include<bits/stdc++.h>

#include "wall.h"

using namespace std;

#define F first
#define S second
#define ll long long
#define maksim gay
// #define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound
#define y1 yy
#define ppb pop_back

const int MAX=2e6+10;
const int inf=2e9;
const int N=2e5;
const int mod=998244353;

int binpow(int a,int n){
  if(n==0)return 1;
  if(n%2)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

struct DO{
  int t[4*MAX],t1[4*MAX];
  int c[4*MAX],c1[4*MAX];

  void build(int v,int tl,int tr){
    t[v]=0;
    t1[v]=1;
    c[v]=0;
    c1[v]=inf;
    if(tl==tr)return;
    int tm=(tl+tr)/2;
    build(2*v,tl,tm);
    build(2*v+1,tm+1,tr);
  }

  void upd(int v,int op,int x){
    if(t1[v]==op){
      if(!op)c1[v]=max(c1[v],x);
      else c1[v]=min(c1[v],x);
    }
    else{
      if(!op)x=max(x,min(c[v],c1[v]));
      else x=min(x,max(c[v],c1[v]));
      c[v]=c1[v];
      c1[v]=x;
      t[v]^=1;
      t1[v]^=1;
    }
    // cout<<v<<" "<<t[v]<<" "<<c[v]<<" "<<t1[v]<<" "<<c1[v]<<"\n";
  }

  void push(int v){
    // cout<<"!!! "<<v<<" "<<t[v]<<" "<<c[v]<<" "<<t1[v]<<" "<<c1[v]<<"\n";
    upd(2*v,t[v],c[v]);
    upd(2*v,t1[v],c1[v]);
    upd(2*v+1,t[v],c[v]);
    upd(2*v+1,t1[v],c1[v]);
    t[v]=0;
    t1[v]=1;
    c[v]=0;
    c1[v]=inf;
  }

  void update(int v,int tl,int tr,int l,int r,int op,int x){
    if(l>r||tl>r||l>tr)return;
    if(l<=tl&&tr<=r){
      upd(v,op,x);
      return;
    }
    push(v);
    int tm=(tl+tr)/2;
    update(2*v,tl,tm,l,r,op,x);
    update(2*v+1,tm+1,tr,l,r,op,x);
  }

  pair<pii,pii> get(int v,int tl,int tr,int pos){
    if(tl==tr){
      return {{t[v],c[v]},{t1[v],c1[v]}};
    }
    int tm=(tl+tr)/2;
    push(v);
    if(pos<=tm)return get(2*v,tl,tm,pos);
    else return get(2*v+1,tm+1,tr,pos);
  }
}t;

void add(int &x,pii y){
  if(y.F==0)x=max(x,y.S);
  else x=min(x,y.S);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<n;i++)finalHeight[i]=0;
  t.build(1,0,n-1);
  for(int i=0;i<k;i++){
    t.update(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
  } 
  for(int i=0;i<n;i++){
    pair<pii,pii> f=t.get(1,0,n-1,i);
    finalHeight[i]=0;
    add(finalHeight[i],f.F);
    add(finalHeight[i],f.S);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 6 ms 6748 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 120 ms 17756 KB Output is correct
3 Correct 196 ms 11912 KB Output is correct
4 Correct 543 ms 21376 KB Output is correct
5 Correct 312 ms 24968 KB Output is correct
6 Correct 261 ms 22696 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 4 ms 6492 KB Output is correct
4 Correct 8 ms 6956 KB Output is correct
5 Correct 9 ms 6744 KB Output is correct
6 Correct 6 ms 6744 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 116 ms 11560 KB Output is correct
9 Correct 191 ms 6768 KB Output is correct
10 Correct 674 ms 17896 KB Output is correct
11 Correct 282 ms 25384 KB Output is correct
12 Correct 269 ms 24144 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 120 ms 17496 KB Output is correct
15 Correct 38 ms 9856 KB Output is correct
16 Correct 806 ms 24432 KB Output is correct
17 Correct 293 ms 24396 KB Output is correct
18 Correct 307 ms 24208 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 8 ms 5008 KB Output is correct
5 Correct 6 ms 6748 KB Output is correct
6 Correct 7 ms 4956 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 118 ms 17640 KB Output is correct
9 Correct 259 ms 14176 KB Output is correct
10 Correct 561 ms 24288 KB Output is correct
11 Correct 269 ms 25048 KB Output is correct
12 Correct 258 ms 24256 KB Output is correct
13 Correct 1 ms 6748 KB Output is correct
14 Correct 120 ms 11344 KB Output is correct
15 Correct 38 ms 5980 KB Output is correct
16 Correct 668 ms 19284 KB Output is correct
17 Correct 289 ms 24208 KB Output is correct
18 Correct 283 ms 17936 KB Output is correct
19 Correct 976 ms 92268 KB Output is correct
20 Correct 1014 ms 89828 KB Output is correct
21 Correct 996 ms 92368 KB Output is correct
22 Correct 955 ms 95764 KB Output is correct
23 Correct 950 ms 95828 KB Output is correct
24 Correct 966 ms 95684 KB Output is correct
25 Correct 955 ms 95780 KB Output is correct
26 Correct 960 ms 98148 KB Output is correct
27 Correct 968 ms 98384 KB Output is correct
28 Correct 965 ms 95824 KB Output is correct
29 Correct 967 ms 95760 KB Output is correct
30 Correct 967 ms 95884 KB Output is correct