oj.uz

Submission #1062732

# Submission time Handle Problem Language Result Execution time Memory
1062732 2024-08-17T10:10:23 Z NemanjaSo2005 Wall (IOI14_wall) C++17
100 / 100
 390 ms 166024 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e6+5;
int N,Q,K,tip[maxn],vis[maxn];
vector<int> poc[maxn],kraj[maxn];
struct slog{
   int res=0,minr=1e9;
} st[maxn];
slog spoj(slog a,slog b){
   slog ret;
   ret.minr=min(a.minr,b.minr);
   ret.res=max(b.res,min(a.res,b.minr));
   return ret;
}
void update(int gde,slog sta){
   gde+=K;
   st[gde]=sta;
   gde/=2;
   while(gde){
      st[gde]=spoj(st[gde*2],st[gde*2+1]);
      gde/=2;
   }
   return;
}
void akt(int x){
   slog sta;
   if(tip[x]==1)
      sta.res=vis[x];
   else
      sta.minr=vis[x];
   update(x,sta);
}
void deakt(int x){
   slog a;
   update(x,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
   N=n;
   Q=k;
   K=1;
   while(K<Q)
      K<<=1;
   for(int i=0;i<Q;i++){
      poc[left[i]].push_back(i);
      kraj[right[i]+1].push_back(i);
      tip[i]=op[i];
      vis[i]=height[i];
   }
   for(int i=0;i<N;i++){
      for(int x:poc[i])
         akt(x);
      for(int x:kraj[i])
         deakt(x);
      finalHeight[i]=st[1].res;
   }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 94292 KB Output is correct
2 Correct 36 ms 94496 KB Output is correct
3 Correct 34 ms 94292 KB Output is correct
4 Correct 36 ms 94804 KB Output is correct
5 Correct 40 ms 94804 KB Output is correct
6 Correct 41 ms 94800 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 94288 KB Output is correct
2 Correct 158 ms 117936 KB Output is correct
3 Correct 128 ms 109516 KB Output is correct
4 Correct 316 ms 133812 KB Output is correct
5 Correct 220 ms 132436 KB Output is correct
6 Correct 222 ms 130388 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 94288 KB Output is correct
2 Correct 37 ms 94556 KB Output is correct
3 Correct 46 ms 94352 KB Output is correct
4 Correct 43 ms 94800 KB Output is correct
5 Correct 45 ms 94800 KB Output is correct
6 Correct 37 ms 94812 KB Output is correct
7 Correct 36 ms 94300 KB Output is correct
8 Correct 157 ms 117944 KB Output is correct
9 Correct 129 ms 109648 KB Output is correct
10 Correct 318 ms 133544 KB Output is correct
11 Correct 233 ms 132404 KB Output is correct
12 Correct 221 ms 130640 KB Output is correct
13 Correct 36 ms 94292 KB Output is correct
14 Correct 157 ms 123832 KB Output is correct
15 Correct 50 ms 97104 KB Output is correct
16 Correct 309 ms 133716 KB Output is correct
17 Correct 216 ms 130644 KB Output is correct
18 Correct 231 ms 130388 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 94288 KB Output is correct
2 Correct 39 ms 94652 KB Output is correct
3 Correct 35 ms 94292 KB Output is correct
4 Correct 36 ms 94800 KB Output is correct
5 Correct 37 ms 94800 KB Output is correct
6 Correct 37 ms 94804 KB Output is correct
7 Correct 37 ms 94292 KB Output is correct
8 Correct 153 ms 117940 KB Output is correct
9 Correct 132 ms 109648 KB Output is correct
10 Correct 322 ms 133460 KB Output is correct
11 Correct 221 ms 132636 KB Output is correct
12 Correct 211 ms 130388 KB Output is correct
13 Correct 35 ms 94296 KB Output is correct
14 Correct 158 ms 123828 KB Output is correct
15 Correct 50 ms 97104 KB Output is correct
16 Correct 315 ms 133676 KB Output is correct
17 Correct 225 ms 130784 KB Output is correct
18 Correct 221 ms 130384 KB Output is correct
19 Correct 351 ms 165968 KB Output is correct
20 Correct 369 ms 163528 KB Output is correct
21 Correct 367 ms 165972 KB Output is correct
22 Correct 390 ms 163480 KB Output is correct
23 Correct 348 ms 163416 KB Output is correct
24 Correct 350 ms 163396 KB Output is correct
25 Correct 350 ms 163408 KB Output is correct
26 Correct 356 ms 165972 KB Output is correct
27 Correct 360 ms 166024 KB Output is correct
28 Correct 364 ms 163408 KB Output is correct
29 Correct 379 ms 163432 KB Output is correct
30 Correct 349 ms 163416 KB Output is correct