oj.uz

Submission #59177

# Submission time Handle Problem Language Result Execution time Memory
59177 2018-07-20T22:12:48 Z TadijaSebez Wall (IOI14_wall) C++11
61 / 100
 1371 ms 263168 KB 
#include "wall.h"
#include <stdio.h>
#include <vector>
using namespace std;
#define pb push_back
const int N=2000050;
const int M=2*N;
const int inf=2e9+7;
int ls[M],rs[M],val[M],lzy1[M],lzy2[M],tsz,root;
int min(int a, int b){ return a>b?b:a;}
int max(int a, int b){ return a>b?a:b;}
void Build(int &c, int ss, int se)
{
	c=++tsz;lzy1[c]=0;lzy2[c]=inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
void Push(int c, int ss, int se)
{
	val[c]=max(val[c],lzy1[c]);
	val[c]=min(val[c],lzy2[c]);
	if(ss!=se)
	{
		lzy1[ls[c]]=max(lzy1[ls[c]],lzy1[c]);
		lzy1[ls[c]]=min(lzy1[ls[c]],lzy2[c]);
		lzy2[ls[c]]=max(lzy2[ls[c]],lzy1[c]);
		lzy2[ls[c]]=min(lzy2[ls[c]],lzy2[c]);
		lzy1[rs[c]]=max(lzy1[rs[c]],lzy1[c]);
		lzy1[rs[c]]=min(lzy1[rs[c]],lzy2[c]);
		lzy2[rs[c]]=max(lzy2[rs[c]],lzy1[c]);
		lzy2[rs[c]]=min(lzy2[rs[c]],lzy2[c]);
	}
	lzy1[c]=0;
	lzy2[c]=inf;
}
void Add(int c, int ss, int se, int qs, int qe, int h)
{
	Push(c,ss,se);
	if(qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ lzy1[c]=h;return;}
	int mid=ss+se>>1;
	Add(ls[c],ss,mid,qs,qe,h);
	Add(rs[c],mid+1,se,qs,qe,h);
}
void Del(int c, int ss, int se, int qs, int qe, int h)
{
	Push(c,ss,se);
	if(qs>se || ss>qe) return;
	if(qs<=ss && qe>=se){ lzy2[c]=h;return;}
	int mid=ss+se>>1;
	Del(ls[c],ss,mid,qs,qe,h);
	Del(rs[c],mid+1,se,qs,qe,h);
}
int sol[N];
void DFS(int c, int ss, int se)
{
	Push(c,ss,se);
	if(ss==se){ sol[ss]=val[c];return;}
	int mid=ss+se>>1;
	DFS(ls[c],ss,mid);
	DFS(rs[c],mid+1,se);
}
void buildWall(int n, int q, int op[], int l[], int r[], int h[], int ans[])
{
	int i;
	Build(root,1,n);
	for(i=0;i<q;i++)
	{
		l[i]++;r[i]++;
		if(op[i]==1) Add(root,1,n,l[i],r[i],h[i]);
		else Del(root,1,n,l[i],r[i],h[i]);
	}
	DFS(root,1,n);
	for(i=1;i<=n;i++) ans[i-1]=sol[i];
}

Compilation message

wall.cpp: In function 'void Build(int&, int, int)':
wall.cpp:16:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void Add(int, int, int, int, int, int)':
wall.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void Del(int, int, int, int, int, int)':
wall.cpp:52:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
wall.cpp: In function 'void DFS(int, int, int)':
wall.cpp:61:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 4 ms 632 KB Output is correct
4 Correct 10 ms 1380 KB Output is correct
5 Correct 12 ms 1380 KB Output is correct
6 Correct 10 ms 1472 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1472 KB Output is correct
2 Correct 199 ms 10460 KB Output is correct
3 Correct 293 ms 10460 KB Output is correct
4 Correct 1076 ms 24908 KB Output is correct
5 Correct 477 ms 35716 KB Output is correct
6 Correct 555 ms 44184 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 44184 KB Output is correct
2 Correct 4 ms 44184 KB Output is correct
3 Correct 4 ms 44184 KB Output is correct
4 Correct 10 ms 44184 KB Output is correct
5 Correct 10 ms 44184 KB Output is correct
6 Correct 14 ms 44184 KB Output is correct
7 Correct 2 ms 44184 KB Output is correct
8 Correct 201 ms 44916 KB Output is correct
9 Correct 287 ms 45116 KB Output is correct
10 Correct 1235 ms 63288 KB Output is correct
11 Correct 519 ms 74080 KB Output is correct
12 Correct 514 ms 82372 KB Output is correct
13 Correct 2 ms 82372 KB Output is correct
14 Correct 182 ms 82568 KB Output is correct
15 Correct 84 ms 82568 KB Output is correct
16 Correct 887 ms 97840 KB Output is correct
17 Correct 456 ms 106664 KB Output is correct
18 Correct 519 ms 115372 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 115372 KB Output is correct
2 Correct 4 ms 115372 KB Output is correct
3 Correct 4 ms 115372 KB Output is correct
4 Correct 13 ms 115372 KB Output is correct
5 Correct 11 ms 115372 KB Output is correct
6 Correct 10 ms 115372 KB Output is correct
7 Correct 2 ms 115372 KB Output is correct
8 Correct 226 ms 115372 KB Output is correct
9 Correct 385 ms 115372 KB Output is correct
10 Correct 885 ms 117444 KB Output is correct
11 Correct 663 ms 127976 KB Output is correct
12 Correct 549 ms 136536 KB Output is correct
13 Correct 3 ms 136536 KB Output is correct
14 Correct 199 ms 137128 KB Output is correct
15 Correct 43 ms 137128 KB Output is correct
16 Correct 968 ms 151492 KB Output is correct
17 Correct 440 ms 151536 KB Output is correct
18 Correct 497 ms 151640 KB Output is correct
19 Correct 1371 ms 255460 KB Output is correct
20 Correct 1180 ms 262136 KB Output is correct
21 Runtime error 1281 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.
22 Halted 0 ms 0 KB -