# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
59893 |
2018-07-23T08:57:05 Z |
hamzqq9 |
Wall (IOI14_wall) |
C++14 |
|
1436 ms |
218620 KB |
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define orta ((bas+son)>>1)
#define N 2000005
struct SEG {
int mn,mx;
} S[N*4];
int lazy[N*4];
int n;
SEG merge(SEG x,SEG y) {
return {min(x.mn,y.mn),max(x.mx,y.mx)};
}
void push(int node,int bas,int son) {
if(~lazy[node]) {
S[node*2].mx=S[node*2].mn=S[node*2+1].mx=S[node*2+1].mn=lazy[node*2]=lazy[node*2+1]=lazy[node];
lazy[node]=-1;
}
}
SEG get(int node,int bas,int son,int x) {
if(bas==x && son==x) return S[node];
push(node,bas,son);
if(orta>=x) return get(node*2,bas,orta,x);
return get(node*2+1,orta+1,son,x);
}
void up(int node,int bas,int son,int l,int r,int h,int typ) {
if(bas>r || son<l) return ;
if(typ==1) {
if(S[node].mn>=h) return ;
}
else {
if(S[node].mx<=h) return ;
}
if(bas>=l && son<=r) {
if(typ==1) {
if(S[node].mx<=h) {
S[node].mx=S[node].mn=h;
lazy[node]=h;
return ;
}
}
else {
if(S[node].mn>=h) {
S[node].mn=S[node].mx=h;
lazy[node]=h;
return ;
}
}
}
if(bas==son) return ;
push(node,bas,son);
up(node*2,bas,orta,l,r,h,typ);
up(node*2+1,orta+1,son,l,r,h,typ);
S[node]=merge(S[node*2],S[node*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(lazy,-1,sizeof(lazy));
::n=n;
for(int i=0;i<k;i++) {
up(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for(int i=0;i<n;i++) {
finalHeight[i]=get(1,0,n-1,i).mx;
}
}
/*
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
int main()
{
freopen("sample-2.in","r",stdin);
int n;
int k;
int i, j;
int status = 0;
status = scanf("%d%d", &n, &k);
assert(status == 2);
int* op = (int*)calloc(sizeof(int), k);
int* left = (int*)calloc(sizeof(int), k);
int* right = (int*)calloc(sizeof(int), k);
int* height = (int*)calloc(sizeof(int), k);
int* finalHeight = (int*)calloc(sizeof(int), n);
for (i = 0; i < k; i++){
status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
assert(status == 4);
}
buildWall(n, k, op, left, right, height, finalHeight);
for (j = 0; j < n; j++)
printf("%d\n", finalHeight[j]);
return 0;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
31608 KB |
Output is correct |
2 |
Correct |
40 ms |
31876 KB |
Output is correct |
3 |
Correct |
32 ms |
31976 KB |
Output is correct |
4 |
Correct |
42 ms |
32440 KB |
Output is correct |
5 |
Correct |
35 ms |
32568 KB |
Output is correct |
6 |
Correct |
34 ms |
32572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
32572 KB |
Output is correct |
2 |
Correct |
315 ms |
45852 KB |
Output is correct |
3 |
Correct |
164 ms |
45852 KB |
Output is correct |
4 |
Correct |
321 ms |
61892 KB |
Output is correct |
5 |
Correct |
376 ms |
65068 KB |
Output is correct |
6 |
Correct |
325 ms |
65068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
65068 KB |
Output is correct |
2 |
Correct |
33 ms |
65068 KB |
Output is correct |
3 |
Correct |
28 ms |
65068 KB |
Output is correct |
4 |
Correct |
33 ms |
65068 KB |
Output is correct |
5 |
Correct |
35 ms |
65068 KB |
Output is correct |
6 |
Correct |
39 ms |
65068 KB |
Output is correct |
7 |
Correct |
29 ms |
65068 KB |
Output is correct |
8 |
Correct |
215 ms |
65068 KB |
Output is correct |
9 |
Correct |
132 ms |
65068 KB |
Output is correct |
10 |
Correct |
314 ms |
65068 KB |
Output is correct |
11 |
Correct |
356 ms |
65792 KB |
Output is correct |
12 |
Correct |
327 ms |
65868 KB |
Output is correct |
13 |
Correct |
31 ms |
65868 KB |
Output is correct |
14 |
Correct |
276 ms |
65868 KB |
Output is correct |
15 |
Correct |
74 ms |
65868 KB |
Output is correct |
16 |
Correct |
769 ms |
65868 KB |
Output is correct |
17 |
Correct |
495 ms |
65868 KB |
Output is correct |
18 |
Correct |
452 ms |
65868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
65868 KB |
Output is correct |
2 |
Correct |
35 ms |
65868 KB |
Output is correct |
3 |
Correct |
29 ms |
65868 KB |
Output is correct |
4 |
Correct |
31 ms |
65868 KB |
Output is correct |
5 |
Correct |
34 ms |
65868 KB |
Output is correct |
6 |
Correct |
33 ms |
65868 KB |
Output is correct |
7 |
Correct |
25 ms |
65868 KB |
Output is correct |
8 |
Correct |
345 ms |
65868 KB |
Output is correct |
9 |
Correct |
151 ms |
65868 KB |
Output is correct |
10 |
Correct |
358 ms |
65868 KB |
Output is correct |
11 |
Correct |
345 ms |
65912 KB |
Output is correct |
12 |
Correct |
294 ms |
65912 KB |
Output is correct |
13 |
Correct |
26 ms |
65912 KB |
Output is correct |
14 |
Correct |
256 ms |
65912 KB |
Output is correct |
15 |
Correct |
63 ms |
65912 KB |
Output is correct |
16 |
Correct |
872 ms |
65912 KB |
Output is correct |
17 |
Correct |
474 ms |
65912 KB |
Output is correct |
18 |
Correct |
485 ms |
65912 KB |
Output is correct |
19 |
Correct |
1322 ms |
113308 KB |
Output is correct |
20 |
Correct |
1436 ms |
121416 KB |
Output is correct |
21 |
Correct |
1291 ms |
134192 KB |
Output is correct |
22 |
Correct |
1031 ms |
142368 KB |
Output is correct |
23 |
Correct |
1030 ms |
152932 KB |
Output is correct |
24 |
Correct |
1303 ms |
163028 KB |
Output is correct |
25 |
Correct |
1247 ms |
173156 KB |
Output is correct |
26 |
Correct |
1253 ms |
185508 KB |
Output is correct |
27 |
Correct |
1179 ms |
194616 KB |
Output is correct |
28 |
Correct |
1203 ms |
201484 KB |
Output is correct |
29 |
Correct |
1152 ms |
210188 KB |
Output is correct |
30 |
Correct |
1178 ms |
218620 KB |
Output is correct |