oj.uz

답안 #1004498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004498 2024-06-21T09:29:14 Z PenguinsAreCute Tiles (BOI24_tiles) C++17
0 / 100
 323 ms 244552 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct seg {
	int s, e, m, v, lazy;
	seg *l, *r;
	seg(int _s, int _e): s(_s), e(_e), m(_s+_e>>1), v(0), lazy(1<<30), l(NULL) {}
	void create() {
		if(!l&&s!=e) {
			l = new seg(s,m);
			r = new seg(m+1,e);
		}
	}
	int val() {return ((~lazy)?lazy*(e-s+1):v);}
	void prop() {
		if(lazy!=-1) {
			l->lazy=lazy;
			r->lazy=lazy;
			lazy=-1;
		}
	}
	void up(int x, int y, int u) {
		if(s==x&&y==e) {lazy=u; return;}
		create();
		prop();
		if(y<=m) l->up(x,y,u);
		else if(x>m) r->up(x,y,u);
		else l->up(x,m,u), r->up(m+1,y,u);
		v=(l->val())+(r->val());
	}
	int qry(int x, int y) {
		if(s==x&&y==e) return val();
		if(lazy!=-1) return (y-x+1)*lazy;
		if(y<=m) return l->qry(x,y);
		if(x>m) return r->qry(x,y);
		return l->qry(x,m)+r->qry(m+1,y);
	}
	int bsta(int x, int u) {
		if(s==e) return ((u?val():(e-s+1)-val())?s:-1);
		create(); prop();
		if(x<=s) {
			if(!(u?val():(e-s+1)-val())) return -1;
			if(u?(l->val()):(e-s+1)-(l->val())) return l->bsta(x,u);
			return r->bsta(x,u);
		}
		if(x>m) return r->bsta(x,u);
		int ans = l->bsta(x,u);
		if(ans==-1) return r->bsta(x,u);
		return ans;
	}
};
main() {
	int n, m; cin >> n >> m;
	seg x(0,1e9), y(0,1e9);
	int xx[n], yy[n];
	vector<vector<int>> ex, ey;
	for(int i=0;i<n;i++) cin>>xx[i]>>yy[i];
	for(int i=0;i<n-1;i++) {
		if(xx[i]==xx[i+1]) ey.push_back({xx[i],yy[i],yy[i+1]});
		else ex.push_back({yy[i],xx[i],xx[i+1]});
	}
	int mxX = m;
	sort(ex.begin(),ex.end());
	sort(ey.begin(),ey.end());
	for(auto v: ex) {
		if(v[1]>v[2]) swap(v[1],v[2]);
		int guy = y.qry(v[1],v[2]-1);
		if(guy>(v[2]-v[1])) {y.up(v[1],v[2]-1,v[0]&1); continue;}
		int erm = y.bsta(v[1],!(v[0]&1));
		y.up(v[1],v[2]-1,1<<30);
		if(erm!=-1&&erm<v[2]) mxX=min(mxX,erm);
	}
	cout << mxX;
}

Compilation message

Main.cpp: In constructor 'seg::seg(long long int, long long int)':
Main.cpp:7:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    7 |  seg(int _s, int _e): s(_s), e(_e), m(_s+_e>>1), v(0), lazy(1<<30), l(NULL) {}
      |                                       ~~^~~
Main.cpp: At global scope:
Main.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 244552 KB Output is correct
2 Correct 149 ms 138420 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 225 ms 173604 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -