oj.uz

Submission #59892

# Submission time Handle Problem Language Result Execution time Memory
59892 2018-07-23T08:51:19 Z hamzqq9 Wall (IOI14_wall) C++14
61 / 100
 1373 ms 263168 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;
}

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31608 KB Output is correct
2 Correct 35 ms 31844 KB Output is correct
3 Correct 28 ms 31980 KB Output is correct
4 Correct 39 ms 32328 KB Output is correct
5 Correct 32 ms 32560 KB Output is correct
6 Correct 34 ms 32560 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 32560 KB Output is correct
2 Correct 299 ms 45964 KB Output is correct
3 Correct 172 ms 45964 KB Output is correct
4 Correct 425 ms 62056 KB Output is correct
5 Correct 340 ms 72756 KB Output is correct
6 Correct 370 ms 81196 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 81196 KB Output is correct
2 Correct 35 ms 81196 KB Output is correct
3 Correct 34 ms 81196 KB Output is correct
4 Correct 36 ms 81196 KB Output is correct
5 Correct 39 ms 81196 KB Output is correct
6 Correct 39 ms 81196 KB Output is correct
7 Correct 33 ms 81196 KB Output is correct
8 Correct 270 ms 84296 KB Output is correct
9 Correct 154 ms 84296 KB Output is correct
10 Correct 313 ms 100356 KB Output is correct
11 Correct 330 ms 110936 KB Output is correct
12 Correct 360 ms 119664 KB Output is correct
13 Correct 30 ms 119664 KB Output is correct
14 Correct 298 ms 122368 KB Output is correct
15 Correct 62 ms 122368 KB Output is correct
16 Correct 838 ms 135284 KB Output is correct
17 Correct 412 ms 144380 KB Output is correct
18 Correct 504 ms 153416 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 153416 KB Output is correct
2 Correct 29 ms 153416 KB Output is correct
3 Correct 32 ms 153416 KB Output is correct
4 Correct 42 ms 153416 KB Output is correct
5 Correct 40 ms 153416 KB Output is correct
6 Correct 45 ms 153416 KB Output is correct
7 Correct 29 ms 153416 KB Output is correct
8 Correct 225 ms 156580 KB Output is correct
9 Correct 166 ms 156580 KB Output is correct
10 Correct 343 ms 172612 KB Output is correct
11 Correct 313 ms 183240 KB Output is correct
12 Correct 374 ms 191928 KB Output is correct
13 Correct 32 ms 191928 KB Output is correct
14 Correct 255 ms 194556 KB Output is correct
15 Correct 77 ms 194556 KB Output is correct
16 Correct 819 ms 207708 KB Output is correct
17 Correct 508 ms 216668 KB Output is correct
18 Correct 527 ms 225576 KB Output is correct
19 Runtime error 1373 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
20 Halted 0 ms 0 KB -