oj.uz

Submission #349457

# Submission time Handle Problem Language Result Execution time Memory
349457 2021-01-17T15:51:22 Z David_M Wall (IOI14_wall) C++14
100 / 100
 933 ms 114540 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=1e9+2021;
struct uwu{int type, height, time; uwu (int x, int y, int z){time=x;type=y;height=z;} };
vector<uwu> v[2<<20];
int T[2][1<<23], M[2], K;
 
void build (int x=1, int l=0, int r=K){
	if(l==r){ T[1][x]=(!!l)*INF; return; }
	build(x<<1, l, l+r>>1);
	build(x<<1|1, l+r+2>>1, r);
	T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
 
void upd(uwu a, int x=1, int l=0, int r=K){
	if(l==r){ T[a.type][x]=a.height; return; }
	int mid=l+r>>1;
	if(a.time<=mid) upd(a, x<<1, l, mid);
	else upd(a, x<<1|1, mid+1, r);
	
	T[0][x]=max(T[0][x<<1], T[0][x<<1|1]);
	T[1][x]=min(T[1][x<<1], T[1][x<<1|1]);
}
 
int get(int x=1, int l=0, int r=K){
	if(l==r){
		M[0]=max(M[0], T[0][x]), 
		M[1]=min(M[1], T[1][x]);
		return (T[0][x]==M[0])?M[1]:M[0];
	}
	int m[]={max(M[0], T[0][x<<1|1]), min(M[1], T[1][x<<1|1])}, mid=l+r>>1;
	if(m[1]>m[0]){ M[0]=m[0]; M[1]=m[1]; return get(x<<1, l, mid); }
	else return get(x<<1|1, mid+1, r);
}
 
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	K=k; build();
 
	for(int i=0; i<k; i++){
		op[i]--;
		v[left[i]].pb({i+1, op[i], height[i]});
		v[right[i]+1].pb({i+1, op[i], op[i]*INF});
	}
	for (int i=0; i<n; i++){
		for (int j=0; j<v[i].size(); j++) upd(v[i][j]);
		M[0]=0; M[1]=INF; finalHeight[i]=get();
	}
}

Compilation message

wall.cpp: In function 'void build(int, int, int)':
wall.cpp:12:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |  build(x<<1, l, l+r>>1);
      |                 ~^~
wall.cpp:13:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |  build(x<<1|1, l+r+2>>1, r);
      |                ~~~^~
wall.cpp: In function 'void upd(uwu, int, int, int)':
wall.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |  int mid=l+r>>1;
      |          ~^~
wall.cpp: In function 'int get(int, int, int)':
wall.cpp:33:67: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  int m[]={max(M[0], T[0][x<<1|1]), min(M[1], T[1][x<<1|1])}, mid=l+r>>1;
      |                                                                  ~^~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<uwu>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int j=0; j<v[i].size(); j++) upd(v[i][j]);
      |                 ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49516 KB Output is correct
2 Correct 33 ms 50028 KB Output is correct
3 Correct 32 ms 49772 KB Output is correct
4 Correct 37 ms 50156 KB Output is correct
5 Correct 37 ms 50156 KB Output is correct
6 Correct 36 ms 50156 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49516 KB Output is correct
2 Correct 332 ms 76980 KB Output is correct
3 Correct 282 ms 64748 KB Output is correct
4 Correct 807 ms 84444 KB Output is correct
5 Correct 516 ms 83948 KB Output is correct
6 Correct 503 ms 81728 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49516 KB Output is correct
2 Correct 33 ms 50028 KB Output is correct
3 Correct 37 ms 49772 KB Output is correct
4 Correct 38 ms 50156 KB Output is correct
5 Correct 37 ms 50156 KB Output is correct
6 Correct 38 ms 50156 KB Output is correct
7 Correct 30 ms 49516 KB Output is correct
8 Correct 329 ms 77108 KB Output is correct
9 Correct 286 ms 64716 KB Output is correct
10 Correct 805 ms 84460 KB Output is correct
11 Correct 505 ms 83820 KB Output is correct
12 Correct 500 ms 81772 KB Output is correct
13 Correct 30 ms 49516 KB Output is correct
14 Correct 330 ms 77492 KB Output is correct
15 Correct 67 ms 52076 KB Output is correct
16 Correct 819 ms 86636 KB Output is correct
17 Correct 503 ms 82924 KB Output is correct
18 Correct 508 ms 82284 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49644 KB Output is correct
2 Correct 33 ms 50028 KB Output is correct
3 Correct 33 ms 49912 KB Output is correct
4 Correct 37 ms 50156 KB Output is correct
5 Correct 37 ms 50156 KB Output is correct
6 Correct 38 ms 50156 KB Output is correct
7 Correct 31 ms 49516 KB Output is correct
8 Correct 328 ms 76980 KB Output is correct
9 Correct 289 ms 64704 KB Output is correct
10 Correct 825 ms 84520 KB Output is correct
11 Correct 508 ms 83900 KB Output is correct
12 Correct 500 ms 81756 KB Output is correct
13 Correct 31 ms 49516 KB Output is correct
14 Correct 327 ms 77492 KB Output is correct
15 Correct 67 ms 52076 KB Output is correct
16 Correct 821 ms 86380 KB Output is correct
17 Correct 508 ms 82796 KB Output is correct
18 Correct 502 ms 82284 KB Output is correct
19 Correct 921 ms 109068 KB Output is correct
20 Correct 917 ms 112108 KB Output is correct
21 Correct 924 ms 114540 KB Output is correct
22 Correct 922 ms 111980 KB Output is correct
23 Correct 933 ms 111988 KB Output is correct
24 Correct 918 ms 111984 KB Output is correct
25 Correct 920 ms 112000 KB Output is correct
26 Correct 930 ms 114412 KB Output is correct
27 Correct 929 ms 114412 KB Output is correct
28 Correct 927 ms 111776 KB Output is correct
29 Correct 922 ms 111876 KB Output is correct
30 Correct 926 ms 111912 KB Output is correct