oj.uz

Submission #930779

# Submission time Handle Problem Language Result Execution time Memory
930779 2024-02-20T12:13:47 Z vjudge1 Wall (IOI14_wall) C++17
0 / 100
 175 ms 17588 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){
    // cout<<op<<"\n";
        // cout<<v<<" "<<t[v]<<" "<<c[v]<<" "<<t1[v]<<" "<<c1[v]<<"\n";

    // cout<<v<<" "<<op<<" "<<x<<"\n";
    if(t1[v]==op){
      if(!op)c1[v]=max(c1[v],x);
      else c1[v]=min(c1[v],x);
    }
    else{
      x=max(x,min(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){
      // cout<<v<<" "<<op<<" "<<x<<"\n";
      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){
      // cout<<t[v]<<" "<<t1[v]<<"\n";
      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++){
    // cout<<op[i]-1<<"\n";
    t.update(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
  }
  pair<pii,pii> f=t.get(1,0,n-1,3);
  // cout<<f.F.F<<" "<<f.F.S<<" "<<f.S.F<<" "<<f.S.S<<"\n";  
  for(int i=0;i<n;i++){
    pair<pii,pii> f=t.get(1,0,n-1,i);
    // cout<<f.F.F<<" "<<f.F.S<<" "<<f.S.F<<" "<<f.S.S<<"\n";
    finalHeight[i]=0;
    add(finalHeight[i],f.F);
    add(finalHeight[i],f.S);
   // cout<<finalHeight[i]<<" ";
  }
//  cout<<"\n";
}

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:118:17: warning: variable 'f' set but not used [-Wunused-but-set-variable]
  118 |   pair<pii,pii> f=t.get(1,0,n-1,3);
      |                 ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 103 ms 17588 KB Output is correct
3 Incorrect 175 ms 13860 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Incorrect 2 ms 6492 KB Output isn't correct
3 Halted 0 ms 0 KB -