oj.uz

Submission #930784

# Submission time Handle Problem Language Result Execution time Memory
930784 2024-02-20T12:16:05 Z shenfe1 Wall (IOI14_wall) C++14
100 / 100
 1199 ms 106936 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 6492 KB Output is correct
3 Correct 2 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 116 ms 14344 KB Output is correct
3 Correct 192 ms 12116 KB Output is correct
4 Correct 539 ms 28092 KB Output is correct
5 Correct 271 ms 29744 KB Output is correct
6 Correct 263 ms 28240 KB Output is correct

Subtask #3
29.0 / 29.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 6656 KB Output is correct
4 Correct 8 ms 6748 KB Output is correct
5 Correct 6 ms 6856 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 116 ms 19800 KB Output is correct
9 Correct 189 ms 15956 KB Output is correct
10 Correct 533 ms 27888 KB Output is correct
11 Correct 273 ms 29828 KB Output is correct
12 Correct 258 ms 28240 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 125 ms 20080 KB Output is correct
15 Correct 37 ms 9928 KB Output is correct
16 Correct 647 ms 28940 KB Output is correct
17 Correct 285 ms 28368 KB Output is correct
18 Correct 279 ms 28368 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 3 ms 6652 KB Output is correct
4 Correct 9 ms 6744 KB Output is correct
5 Correct 6 ms 6748 KB Output is correct
6 Correct 6 ms 6748 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 117 ms 19772 KB Output is correct
9 Correct 193 ms 15908 KB Output is correct
10 Correct 526 ms 27984 KB Output is correct
11 Correct 281 ms 29748 KB Output is correct
12 Correct 258 ms 28184 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 124 ms 20228 KB Output is correct
15 Correct 45 ms 9820 KB Output is correct
16 Correct 659 ms 28948 KB Output is correct
17 Correct 299 ms 28540 KB Output is correct
18 Correct 312 ms 28500 KB Output is correct
19 Correct 1002 ms 105052 KB Output is correct
20 Correct 986 ms 106188 KB Output is correct
21 Correct 1036 ms 105112 KB Output is correct
22 Correct 1065 ms 106196 KB Output is correct
23 Correct 989 ms 102564 KB Output is correct
24 Correct 1199 ms 102572 KB Output is correct
25 Correct 1016 ms 102484 KB Output is correct
26 Correct 993 ms 105128 KB Output is correct
27 Correct 972 ms 106936 KB Output is correct
28 Correct 993 ms 103380 KB Output is correct
29 Correct 986 ms 106188 KB Output is correct
30 Correct 979 ms 106320 KB Output is correct