Submission #1004508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004508		PenguinsAreCute	Tiles (BOI24_tiles)	C++17	0 / 100	342 ms	240836 KiB

Main

#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]});
	}
	if(xx[n-1]==xx[0]) ey.push_back({xx[0],yy[0],yy[n-1]});
	else ex.push_back({yy[0],xx[0],xx[n-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 (stderr)

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 22
• Subtask 6: 0 / 25
• Subtask 7: 0 / 10