oj.uz

Submission #197711

# Submission time Handle Problem Language Result Execution time Memory
197711 2020-01-22T13:17:27 Z arnold518 Wall (IOI14_wall) C++14
100 / 100
 893 ms 106232 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;
const int MAXK = 5e5;
const int INF = 987654321;

int N, K;
int O[MAXK+10], L[MAXK+10], R[MAXK+10], H[MAXK+10], ans[MAXN+10];

struct Node
{
	int l, r;
	Node() : l(0), r(INF) {}
	Node(int l, int r) : l(l), r(r) {}
};

Node tree[MAXN*4+10];

Node operator + (const Node &p, const Node &q)
{
	if(q.r<=p.l) return Node(q.r, q.r);
	if(p.r<=q.l) return Node(q.l, q.l);
	return Node(max(p.l, q.l), min(p.r, q.r));
}

void update(int node, int tl, int tr, int l, int r, int k)
{
	if(tl!=tr)
	{
		tree[node*2]=tree[node*2]+tree[node];
		tree[node*2+1]=tree[node*2+1]+tree[node];
		tree[node]=Node();
	}
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		Node t;
		if(O[k]==1) t.l=H[k];
		if(O[k]==2) t.r=H[k];
		tree[node]=tree[node]+t;
		return;
	}
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
}

void query(int node, int tl, int tr)
{
	if(tl!=tr)
	{
		tree[node*2]=tree[node*2]+tree[node];
		tree[node*2+1]=tree[node*2+1]+tree[node];
		tree[node]=Node();
	}
	else
	{
		ans[tl]=tree[node].l;
		return;
	}
	int mid=tl+tr>>1;
	query(node*2, tl, mid);
	query(node*2+1, mid+1, tr);
}

void buildWall(int _N, int _K, int *_O, int *_L, int *_R, int *_H, int finalHeight[])
{
	int i, j;

	N=_N; K=_K;
	for(i=1; i<=K; i++) O[i]=_O[i-1], L[i]=_L[i-1]+1, R[i]=_R[i-1]+1, H[i]=_H[i-1];

	for(i=1; i<=K; i++) update(1, 1, N, L[i], R[i], i);
	query(1, 1, N);
	for(i=1; i<=N; i++) finalHeight[i-1]=ans[i];
}

Compilation message

wall.cpp: In function 'void update(int, int, int, int, int, int)':
wall.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void query(int, int, int)':
wall.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:74:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62968 KB Output is correct
2 Correct 59 ms 63188 KB Output is correct
3 Correct 58 ms 62968 KB Output is correct
4 Correct 65 ms 63352 KB Output is correct
5 Correct 63 ms 63312 KB Output is correct
6 Correct 63 ms 63352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 63004 KB Output is correct
2 Correct 238 ms 83420 KB Output is correct
3 Correct 260 ms 73468 KB Output is correct
4 Correct 667 ms 81656 KB Output is correct
5 Correct 410 ms 82296 KB Output is correct
6 Correct 405 ms 81912 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62968 KB Output is correct
2 Correct 59 ms 63224 KB Output is correct
3 Correct 59 ms 63136 KB Output is correct
4 Correct 65 ms 63272 KB Output is correct
5 Correct 62 ms 63352 KB Output is correct
6 Correct 61 ms 63324 KB Output is correct
7 Correct 57 ms 62968 KB Output is correct
8 Correct 238 ms 83576 KB Output is correct
9 Correct 261 ms 73520 KB Output is correct
10 Correct 634 ms 81760 KB Output is correct
11 Correct 409 ms 82184 KB Output is correct
12 Correct 402 ms 81912 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 243 ms 83576 KB Output is correct
15 Correct 99 ms 64760 KB Output is correct
16 Correct 871 ms 81912 KB Output is correct
17 Correct 427 ms 81784 KB Output is correct
18 Correct 424 ms 81832 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62968 KB Output is correct
2 Correct 58 ms 63208 KB Output is correct
3 Correct 58 ms 63096 KB Output is correct
4 Correct 64 ms 63424 KB Output is correct
5 Correct 62 ms 63352 KB Output is correct
6 Correct 62 ms 63352 KB Output is correct
7 Correct 57 ms 62968 KB Output is correct
8 Correct 237 ms 80200 KB Output is correct
9 Correct 260 ms 73488 KB Output is correct
10 Correct 639 ms 81212 KB Output is correct
11 Correct 423 ms 81784 KB Output is correct
12 Correct 404 ms 81400 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 243 ms 79992 KB Output is correct
15 Correct 98 ms 64760 KB Output is correct
16 Correct 893 ms 81376 KB Output is correct
17 Correct 425 ms 81272 KB Output is correct
18 Correct 423 ms 81268 KB Output is correct
19 Correct 841 ms 106232 KB Output is correct
20 Correct 831 ms 103848 KB Output is correct
21 Correct 841 ms 105968 KB Output is correct
22 Correct 858 ms 103284 KB Output is correct
23 Correct 837 ms 103296 KB Output is correct
24 Correct 863 ms 103264 KB Output is correct
25 Correct 834 ms 103288 KB Output is correct
26 Correct 867 ms 106016 KB Output is correct
27 Correct 844 ms 105772 KB Output is correct
28 Correct 834 ms 102856 KB Output is correct
29 Correct 835 ms 102852 KB Output is correct
30 Correct 837 ms 102820 KB Output is correct