oj.uz

Submission #125028

# Submission time Handle Problem Language Result Execution time Memory
125028 2019-07-04T12:00:05 Z baluteshih Wall (IOI14_wall) C++14
100 / 100
 710 ms 83832 KB 
#include "wall.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define MEM(i,j) memset(i,j,sizeof i)
#define MP make_pair
#define pii pair<int,int> 
#define pll pair<long long,long long>
#define ET cout << "\n"
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;

struct node
{
	int U,D;
}seg[6000004];

const int INF = 100000;

inline void add(int a,int x)
{
	if(!~seg[a].U) seg[a].D=max(seg[a].D,x);
	else
		if(x>=seg[a].U) seg[a].U=-1,seg[a].D=x;
		else seg[a].D=max(seg[a].D,x);
}

inline void remove(int a,int x)
{
	if(!~seg[a].U) seg[a].D=min(seg[a].D,x);
	else 
		if(x<=seg[a].D) seg[a].U=-1,seg[a].D=x;
		else seg[a].U=min(seg[a].U,x);
}

inline void down(int l,int r,int rt)
{
	if(l==r) return;
	if(!~seg[rt].U) 
		seg[rt<<1].U=-1,seg[rt<<1].D=seg[rt].D,seg[rt<<1|1].U=-1,seg[rt<<1|1].D=seg[rt].D;
	else 
	{
		if(seg[rt].D!=0) add(rt<<1,seg[rt].D),add(rt<<1|1,seg[rt].D);
		if(seg[rt].U!=INF) remove(rt<<1,seg[rt].U),remove(rt<<1|1,seg[rt].U);
	}
	seg[rt].U=INF,seg[rt].D=0;
}

void modify(int L,int R,int l,int r,int rt,int x,int type)
{
	down(l,r,rt);
	if(L<=l && R>=r)
	{
		if(type==1) add(rt,x);
		else remove(rt,x);
		return;
	}
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,x,type);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,x,type);
}

void all(int l,int r,int rt,int finalHeight[])
{
	down(l,r,rt);
	if(l==r) return finalHeight[l]=seg[rt].D,void();
	int m=l+r>>1;
	all(l,m,rt<<1,finalHeight),all(m+1,r,rt<<1|1,finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<3*n;++i) seg[i].U=-1,seg[i].D=0;
	for(int i=0;i<k;++i) modify(left[i],right[i],0,n-1,1,height[i],op[i]);
	all(0,n-1,1,finalHeight);
}

Compilation message

wall.cpp: In function 'void modify(int, int, int, int, int, int, int)':
wall.cpp:61:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~
wall.cpp: In function 'void all(int, int, int, int*)':
wall.cpp:70:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=l+r>>1;
        ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 792 KB Output is correct
6 Correct 6 ms 888 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 175 ms 13892 KB Output is correct
3 Correct 188 ms 8184 KB Output is correct
4 Correct 540 ms 20728 KB Output is correct
5 Correct 285 ms 21752 KB Output is correct
6 Correct 268 ms 20216 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 176 ms 14028 KB Output is correct
9 Correct 186 ms 8056 KB Output is correct
10 Correct 532 ms 20692 KB Output is correct
11 Correct 288 ms 21852 KB Output is correct
12 Correct 267 ms 20216 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 178 ms 13940 KB Output is correct
15 Correct 34 ms 2192 KB Output is correct
16 Correct 600 ms 20960 KB Output is correct
17 Correct 288 ms 20396 KB Output is correct
18 Correct 270 ms 20348 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 8 ms 820 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 175 ms 14064 KB Output is correct
9 Correct 194 ms 8056 KB Output is correct
10 Correct 536 ms 20680 KB Output is correct
11 Correct 286 ms 21880 KB Output is correct
12 Correct 267 ms 20216 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 181 ms 13944 KB Output is correct
15 Correct 33 ms 2040 KB Output is correct
16 Correct 551 ms 21064 KB Output is correct
17 Correct 277 ms 20344 KB Output is correct
18 Correct 271 ms 20476 KB Output is correct
19 Correct 652 ms 83652 KB Output is correct
20 Correct 654 ms 81144 KB Output is correct
21 Correct 651 ms 83832 KB Output is correct
22 Correct 643 ms 81240 KB Output is correct
23 Correct 655 ms 81448 KB Output is correct
24 Correct 646 ms 81192 KB Output is correct
25 Correct 644 ms 81284 KB Output is correct
26 Correct 654 ms 83592 KB Output is correct
27 Correct 710 ms 83700 KB Output is correct
28 Correct 650 ms 81268 KB Output is correct
29 Correct 647 ms 81200 KB Output is correct
30 Correct 652 ms 81260 KB Output is correct