oj.uz

Submission #197705

# Submission time Handle Problem Language Result Execution time Memory
197705 2020-01-22T13:07:31 Z arnold518 Wall (IOI14_wall) C++14
0 / 100
 237 ms 84632 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)
	{
		if(O[k]==1) tree[node].l=H[k];
		if(O[k]==2) tree[node].r=H[k];
		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();
	}
	if(tl==tr) { printf("%d %d : %d %d\n", tl, tr, tree[node].l, tree[node].r); 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:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void query(int, int, int)':
wall.cpp:65:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
wall.cpp: In function 'void debug(int, int, int)':
wall.cpp:79: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:86:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 63096 KB Output is correct
2 Incorrect 60 ms 63224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63064 KB Output is correct
2 Incorrect 237 ms 84632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 63096 KB Output is correct
2 Incorrect 69 ms 63224 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 63100 KB Output is correct
2 Incorrect 59 ms 63128 KB Output isn't correct
3 Halted 0 ms 0 KB -