oj.uz

Submission #197710

# Submission time Handle Problem Language Result Execution time Memory
197710 2020-01-22T13:16:28 Z arnold518 Wall (IOI14_wall) C++14
100 / 100
 892 ms 115132 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 debug(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();
	}*/
	printf("%d %d : %d %d\n", tl, tr, tree[node].l, tree[node].r);
	if(tl==tr) {  return; }
	int mid=tl+tr>>1;
	debug(node*2, tl, mid);
	debug(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);
		//debug(1, 1, N);
		//printf("\n");
	}
	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 debug(int, int, int)':
wall.cpp:83: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:90: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 63096 KB Output is correct
3 Correct 59 ms 63096 KB Output is correct
4 Correct 64 ms 63480 KB Output is correct
5 Correct 62 ms 63356 KB Output is correct
6 Correct 62 ms 63352 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62904 KB Output is correct
2 Correct 235 ms 78812 KB Output is correct
3 Correct 262 ms 73632 KB Output is correct
4 Correct 648 ms 89332 KB Output is correct
5 Correct 420 ms 90288 KB Output is correct
6 Correct 416 ms 88696 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 63096 KB Output is correct
3 Correct 60 ms 63068 KB Output is correct
4 Correct 65 ms 63376 KB Output is correct
5 Correct 62 ms 63300 KB Output is correct
6 Correct 62 ms 63368 KB Output is correct
7 Correct 57 ms 62956 KB Output is correct
8 Correct 236 ms 84492 KB Output is correct
9 Correct 259 ms 73472 KB Output is correct
10 Correct 652 ms 89488 KB Output is correct
11 Correct 420 ms 90264 KB Output is correct
12 Correct 440 ms 88696 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 240 ms 84584 KB Output is correct
15 Correct 101 ms 64888 KB Output is correct
16 Correct 878 ms 89592 KB Output is correct
17 Correct 429 ms 88952 KB Output is correct
18 Correct 429 ms 88952 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 62968 KB Output is correct
2 Correct 59 ms 63120 KB Output is correct
3 Correct 59 ms 63096 KB Output is correct
4 Correct 64 ms 63436 KB Output is correct
5 Correct 62 ms 63480 KB Output is correct
6 Correct 62 ms 63352 KB Output is correct
7 Correct 64 ms 62932 KB Output is correct
8 Correct 236 ms 84472 KB Output is correct
9 Correct 262 ms 73592 KB Output is correct
10 Correct 642 ms 89360 KB Output is correct
11 Correct 423 ms 90440 KB Output is correct
12 Correct 414 ms 88696 KB Output is correct
13 Correct 57 ms 62968 KB Output is correct
14 Correct 241 ms 84444 KB Output is correct
15 Correct 99 ms 64760 KB Output is correct
16 Correct 892 ms 89592 KB Output is correct
17 Correct 435 ms 88952 KB Output is correct
18 Correct 436 ms 88952 KB Output is correct
19 Correct 849 ms 115064 KB Output is correct
20 Correct 847 ms 112548 KB Output is correct
21 Correct 847 ms 115064 KB Output is correct
22 Correct 841 ms 112632 KB Output is correct
23 Correct 852 ms 112564 KB Output is correct
24 Correct 846 ms 112540 KB Output is correct
25 Correct 840 ms 112604 KB Output is correct
26 Correct 860 ms 115132 KB Output is correct
27 Correct 851 ms 114828 KB Output is correct
28 Correct 839 ms 112680 KB Output is correct
29 Correct 855 ms 112676 KB Output is correct
30 Correct 848 ms 112632 KB Output is correct