oj.uz

답안 #586582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586582 2022-06-30T12:02:34 Z LastRonin 벽 (IOI14_wall) C++14
100 / 100
 961 ms 123856 KB 
#include "wall.h"  
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define ll long long
#define mp make_pair

const int N = 5e5 + 10;

ll K;

struct seg {
	ll t[4 * N] = {0};
	ll t2[4 * N] = {0};
	void upd1(ll p, ll z, ll v = 1, ll tl = 0, ll tr = K) {
		if(tl == tr) {
			t[v] = z;
			return;
		}          
		ll m = (tl + tr) >> 1ll;
		if(p <= m)upd1(p, z, v * 2, tl, m);
		else upd1(p, z, v * 2 + 1, m + 1, tr);
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	void upd2(ll p, ll z, ll v = 1, ll tl = 0, ll tr = K) {
		if(tl == tr) {
			t2[v] = z;
			return;   
		}          
		ll m = (tl + tr) >> 1ll;
		if(p <= m)upd2(p, z, v * 2, tl, m);
		else upd2(p, z, v * 2 + 1, m + 1, tr);
		t2[v] = min(t2[v * 2], t2[v * 2 + 1]);
	}
	ll get2(ll p, ll v = 1, ll tl = 0, ll tr = K) {
		if(tl == tr) {
			return t[v];   
		}          
		ll m = (tl + tr) >> 1ll;
		if(p <= m)
			return max(get2(p, v * 2, tl, m), t[v * 2 + 1]);
		return get2(p, v * 2 + 1, m + 1, tr);
	}
	ll get3(ll p, ll v = 1, ll tl = 0, ll tr = K) {
		if(tl == tr) {
			return t2[v];   
		}          
		ll m = (tl + tr) >> 1ll;
		if(p <= m)
			return min(get3(p, v * 2, tl, m), t2[v * 2 + 1]);
		return get3(p, v * 2 + 1, m + 1, tr);
	}
	ll get(ll x, ll y, ll v = 1, ll tl = 0, ll tr = K) {
		if(tl == tr) {
			return tl;
		}
		ll m = (tl + tr) >> 1ll;
		ll a = max(x, t[v * 2 + 1]);
		ll b = min(y, t2[v * 2 + 1]);
		if(a > b)
			return get(x, y, v * 2 + 1, m + 1, tr);
		return get(a, b, v * 2, tl, m); 
	}
} rt;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<int> g[n + 1];
    K = k;
    rt.upd1(0, 1e9);
    rt.upd2(0, 0);
    for(int i = 0; i < k; i++) {
    	g[left[i]].pb(i);
		g[right[i] + 1].pb(i);
		rt.upd2(i + 1, 1e9);
		rt.upd1(i + 1, 0);
    }
    ll cnt = 0;
    for(int i = 0; i < n; i++) {
    	for(auto u : g[i]) {
    		if(left[u] == i) {
    			if(op[u] == 1) rt.upd1(u + 1, height[u]);
    			if(op[u] == 2) rt.upd2(u + 1, height[u]);
    		} else {
    			if(op[u] == 1) rt.upd1(u + 1, 0);
    			if(op[u] == 2) rt.upd2(u + 1, 1e9);
    		}
    	}
		//if(i == 3)cout << "________________________";
//		cout << "here " << i << " : ";
    	ll pos = rt.get(0, 1e9);
    	ll xs = rt.get2(pos), ys = rt.get3(pos);
    	ll xe = rt.get2(pos + 1), ye = rt.get3(pos + 1);
//    	cout << pos << "\n";
//    	cout << xs << " " << ys << "\n";
//    	cout << xe << " " << ye << "\n";
    	if(pos == 0) finalHeight[i] = xe;
    	if(xe == xs) finalHeight[i] = xe;
    	if(ye == ys) finalHeight[i] = ye;
    	//ll y = rt.get3(pos);
    	
    	//if(finalHeight[i] == 1e9)final
    	//if(i == 3)cout << "________________________";

    }
	return;
}
/*
int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}
/*
10 6 1 1 8 4 2 4 9 1 2 3 6 5 1 0 5 3 1 2 2 5 2 6 7 0
*/

Compilation message

wall.cpp:139:1: warning: "/*" within comment [-Wcomment]
  139 | /*
      |  
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:79:8: warning: unused variable 'cnt' [-Wunused-variable]
   79 |     ll cnt = 0;
      |        ^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 6 ms 1216 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 7 ms 1240 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 237 ms 34416 KB Output is correct
3 Correct 197 ms 19052 KB Output is correct
4 Correct 618 ms 45064 KB Output is correct
5 Correct 338 ms 44540 KB Output is correct
6 Correct 322 ms 42828 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 1216 KB Output is correct
5 Correct 7 ms 1188 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 241 ms 34500 KB Output is correct
9 Correct 176 ms 18956 KB Output is correct
10 Correct 594 ms 45200 KB Output is correct
11 Correct 336 ms 44536 KB Output is correct
12 Correct 330 ms 42872 KB Output is correct
13 Correct 0 ms 316 KB Output is correct
14 Correct 246 ms 34416 KB Output is correct
15 Correct 30 ms 3568 KB Output is correct
16 Correct 645 ms 45292 KB Output is correct
17 Correct 342 ms 43216 KB Output is correct
18 Correct 349 ms 43316 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 1208 KB Output is correct
5 Correct 6 ms 1236 KB Output is correct
6 Correct 7 ms 1236 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 238 ms 34396 KB Output is correct
9 Correct 183 ms 19020 KB Output is correct
10 Correct 588 ms 45028 KB Output is correct
11 Correct 332 ms 44540 KB Output is correct
12 Correct 323 ms 42780 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 243 ms 34484 KB Output is correct
15 Correct 30 ms 3492 KB Output is correct
16 Correct 631 ms 45504 KB Output is correct
17 Correct 344 ms 43220 KB Output is correct
18 Correct 344 ms 43416 KB Output is correct
19 Correct 945 ms 123604 KB Output is correct
20 Correct 947 ms 121140 KB Output is correct
21 Correct 937 ms 123856 KB Output is correct
22 Correct 939 ms 121108 KB Output is correct
23 Correct 939 ms 121152 KB Output is correct
24 Correct 932 ms 121108 KB Output is correct
25 Correct 949 ms 121108 KB Output is correct
26 Correct 952 ms 123684 KB Output is correct
27 Correct 949 ms 123628 KB Output is correct
28 Correct 961 ms 120960 KB Output is correct
29 Correct 954 ms 121180 KB Output is correct
30 Correct 944 ms 121164 KB Output is correct