oj.uz

Submission #1004554

# Submission time Handle Problem Language Result Execution time Memory
1004554 2024-06-21T09:45:35 Z PenguinsAreCute Tiles (BOI24_tiles) C++17
0 / 100
 379 ms 243888 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;
			v=(e-s+1)*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

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:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   53 | main() {
      | ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 239784 KB Output is correct
2 Correct 163 ms 135864 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 262 ms 173640 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 214 ms 29224 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 364 ms 204964 KB Output is correct
9 Correct 182 ms 18612 KB Output is correct
10 Correct 379 ms 156328 KB Output is correct
11 Correct 319 ms 243888 KB Output is correct
12 Correct 272 ms 173592 KB Output is correct
13 Correct 172 ms 18352 KB Output is correct
14 Correct 198 ms 18600 KB Output is correct
15 Incorrect 184 ms 18716 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -