oj.uz

Submission #1043507

# Submission time Handle Problem Language Result Execution time Memory
1043507 2024-08-04T10:19:39 Z Malix Wall (IOI14_wall) C++14
100 / 100
 2130 ms 26308 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))
 
ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

void buildWall(int n, int k, int t[], int l[], int r[], int h[], int finalHeight[]){
  vi ans(n,0);
  int m=sqrt(n);
  vi b(m+2,0),c(m+2,inf);
  REP(i,0,k){
    int x=l[i]/m;
    int y=r[i]/m;
    REP(j,x+1,y){
      if(t[i]==1){
        b[j]=max(b[j],h[i]);
        c[j]=max(c[j],h[i]);
      }
      else{
        c[j]=min(c[j],h[i]);
        b[j]=min(b[j],h[i]);
      }
    }
    REP(j,x*m,min(n,x*m+m)){
      ans[j]=min(ans[j],c[x]);
      ans[j]=max(ans[j],b[x]);
    }
    b[x]=0;c[x]=inf;
    REP(j,y*m,min(n,y*m+m)){
      ans[j]=min(ans[j],c[y]);
      ans[j]=max(ans[j],b[y]);
    }
    b[y]=0;c[y]=inf;
    REP(j,l[i],min(min(n,x*m+m),r[i]+1)){
      if(t[i]==1)ans[j]=max(ans[j],h[i]);
      else ans[j]=min(ans[j],h[i]);
    }
    REP(j,max(l[i],y*m),r[i]+1){
      if(t[i]==1)ans[j]=max(ans[j],h[i]);
      else ans[j]=min(ans[j],h[i]);
    }
  }
  REP(j,0,n){
    ans[j]=min(ans[j],c[j/m]);
    ans[j]=max(ans[j],b[j/m]);
  }
  REP(i,0,n)finalHeight[i]=ans[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 67 ms 8040 KB Output is correct
3 Correct 109 ms 3668 KB Output is correct
4 Correct 471 ms 9044 KB Output is correct
5 Correct 348 ms 9160 KB Output is correct
6 Correct 313 ms 9160 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 68 ms 8076 KB Output is correct
9 Correct 105 ms 3808 KB Output is correct
10 Correct 474 ms 8816 KB Output is correct
11 Correct 331 ms 9160 KB Output is correct
12 Correct 312 ms 9292 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 70 ms 8220 KB Output is correct
15 Correct 16 ms 1112 KB Output is correct
16 Correct 484 ms 9084 KB Output is correct
17 Correct 342 ms 8944 KB Output is correct
18 Correct 364 ms 9036 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 67 ms 8048 KB Output is correct
9 Correct 117 ms 3820 KB Output is correct
10 Correct 478 ms 9044 KB Output is correct
11 Correct 328 ms 9100 KB Output is correct
12 Correct 340 ms 9340 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 81 ms 8028 KB Output is correct
15 Correct 18 ms 1116 KB Output is correct
16 Correct 494 ms 9040 KB Output is correct
17 Correct 327 ms 9044 KB Output is correct
18 Correct 333 ms 9040 KB Output is correct
19 Correct 1978 ms 26220 KB Output is correct
20 Correct 1991 ms 23888 KB Output is correct
21 Correct 2021 ms 26308 KB Output is correct
22 Correct 2130 ms 23840 KB Output is correct
23 Correct 2062 ms 23892 KB Output is correct
24 Correct 1996 ms 23888 KB Output is correct
25 Correct 2084 ms 23788 KB Output is correct
26 Correct 2110 ms 26216 KB Output is correct
27 Correct 2009 ms 26196 KB Output is correct
28 Correct 2101 ms 23892 KB Output is correct
29 Correct 2090 ms 23816 KB Output is correct
30 Correct 2089 ms 23788 KB Output is correct