| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1014182 |
2024-07-04T13:43:48 Z |
hengliao |
Tiles (BOI24_tiles) |
C++17 |
|
69 ms |
13260 KB |
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
ll n, m;
set<ll> lef;
set<ll> rig;
vector<pll> pts;
vector<pair<ll, pll>> seg;
vll con;
ll dumb;
bool inside(ll y){
if(lef.upper_bound(y)==lef.begin()) return 0;
auto it=prev(lef.upper_bound(y));
auto it2=rig.lower_bound(y);
if(it==lef.end() || it2==rig.end()){
return 0;
}
ll f=*it;
ll s=*it2;
if(f<s){
return 1;
}
return 0;
}
void solve(){
cin>>n>>m;
pts.resize(n);
for(ll i=0;i<n;i++){
cin>>pts[i].F>>pts[i].S;
con.pb(pts[i].F);
}
for(ll i=0;i<n-1;i++){
if(pts[i].F==pts[i+1].F){
seg.pb({pts[i].F, {min(pts[i].S, pts[i+1].S), max(pts[i].S, pts[i+1].S)}});
}
}
if(pts[n-1].F==pts[0].F){
seg.pb({pts[0].F, {min(pts[0].S, pts[n-1].S), max(pts[0].S, pts[n-1].S)}});
}
sort(seg.begin(), seg.end());
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
ll p=0;
dumb=0;
for(auto &x:con){
if(x%2==1){
cout<<x-1<<'\n';
return;
}
while(p<n && seg[p].F<=x){
//cout<<"______\n";
//cout<<seg[p].F<<' '<<seg[p].S.F<<' '<<seg[p].S.S<<'\n';
if(x==0){
lef.insert(seg[p].S.F);
rig.insert(seg[p].S.S);
if((seg[p].S.S-seg[p].S.F)%2==1){
dumb--;
}
}
else{
if(inside(seg[p].S.F) && inside(seg[p].S.S)){
//cout<<"bruh\n";
ll orgl=*prev(lef.upper_bound(seg[p].S.F));
ll orgr=*rig.lower_bound(seg[p].S.S);
if((seg[p].S.F-orgl)%2==1){
dumb--;
rig.insert(seg[p].S.F);
}
else if(seg[p].S.F-orgl==0){
lef.erase(orgl);
}
else{
rig.insert(seg[p].S.F);
}
if((orgr-seg[p].S.S)%2==1){
dumb--;
lef.insert(seg[p].S.S);
}
else if(seg[p].S.S-orgr==0){
rig.erase(orgr);
}
else{
lef.insert(seg[p].S.S);
}
}
else{
if(inside(seg[p].S.F)){
//cout<<"damn\n";
rig.erase(seg[p].S.F);
rig.insert(seg[p].S.S);
ll orgl=*prev(lef.lower_bound(seg[p].S.F));
if((seg[p].S.S-orgl)%2==0 && (seg[p].S.F-orgl)%2==1){
dumb++;
}
else if((seg[p].S.S-orgl)%2==1 && (seg[p].S.F-orgl)%2==0){
dumb--;
}
}
else{
//cout<<"hi\n";
lef.erase(seg[p].S.S);
lef.insert(seg[p].S.F);
ll orgr=*rig.lower_bound(seg[p].S.S);
if((orgr-seg[p].S.F)%2==0 && (orgr-seg[p].S.S)%2==1){
dumb++;
}
else if((orgr-seg[p].S.F)%2==1 && (orgr-seg[p].S.S)%2==0){
dumb--;
}
}
}
}
p++;
/*cout<<x<<'\n';
for(auto &it:lef){
cout<<it<<' ';
}
cout<<'\n';
for(auto &it:rig){
cout<<it<<' ';
}
cout<<'\n';*/
}
auto it=lef.begin();
for(auto &r:rig){
if((r-*it)%2==1){
cout<<x<<'\n';
return;
}
it=next(it);
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
36 ms |
6964 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
13260 KB |
Output is correct |
| 2 |
Incorrect |
37 ms |
7124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
