| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1079386 |
2024-08-28T13:46:36 Z |
anton |
Tiles (BOI24_tiles) |
C++17 |
|
2000 ms |
17068 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pt complex<int>
#define pii pair<int, int>
int N, M;
struct Interval{
int x;
int yl, yr;
bool open = false;
bool operator<(const Interval& b)const{
return yl<b.yl;
}
vector<Interval> clip(pii other_pair){
////cout<<"clipping "<<yl<<" "<<yr<<" "<<other_pair.first<<" "<<other_pair.second<<endl;
if(yr<other_pair.first || other_pair.second<yl){
return {*this};
}
if(yl<=other_pair.first && other_pair.second<=yr){
return {Interval{x, yl, other_pair.first-1, open}, Interval{x, other_pair.second+1, yr, open}};
}
if(other_pair.first<= yl && yr<=other_pair.second){
return {Interval{x, 0, -1, open}};
}
if(other_pair.first<=yl && other_pair.second<=yr){
return {Interval{x, other_pair.second+1, yr, open}};
}
if(other_pair.first>=yl && other_pair.second>=yr){
return {Interval{x, yl, other_pair.first-1, open}};
}
assert(false);
}
bool is_valid(){
return yl<=yr;
}
};
struct InterSet{
set<Interval> intervals;
bool is_valid = true;
int last_valid = 1e18;
void insert(Interval new_inter){
//cout<<"inserting "<<new_inter.yl<<" "<<new_inter.yr<<endl;
auto lb = intervals.upper_bound(new_inter);
if(lb!=intervals.begin()){
--lb;
}
auto rb = intervals.upper_bound(Interval{0, new_inter.yr, new_inter.yr, false});
if(rb!= intervals.end()){
++rb;
}
for(auto it = intervals.begin(); it!= rb;){
Interval val = *it;
it = intervals.erase(it);
vector<Interval>resulting = val.clip({new_inter.yl, new_inter.yr});
for(auto val2: resulting){
if(!new_inter.open){
if(pii({val.yl, val.yr}) != pii({val2.yl, val2.yr})){
if(is_valid && (new_inter.x-val.x)%2==1){
last_valid = new_inter.x-1;
////cout<<"breaking is "<<new_inter.yl<<" "<<new_inter.yr<<endl;
}
is_valid &= (new_inter.x-val.x)%2==0;
}
}
if(val2.is_valid()){
intervals.insert(val2);
}
}
}
if(new_inter.open){
intervals.insert(new_inter);
}
for(auto e: intervals){
//cout<<e.yl<<" "<<e.yr<<" ";
}
//cout<<endl;
}
};
signed main(){
cin>>N>>M;
vector<pt> pts;
for(int i = 0; i<N; i++){
int a, b;
cin>>a>>b;
pts.push_back({a, b});
}
vector<pair<pt, pt>> edges;
pt prev= pts.back();
for(int i = 0; i<N; i++){
edges.push_back({prev, pts[i]-prev});
prev = pts[i];
}
int area = 0;
for(auto e: edges){
area += e.first.imag() * e.second.real();
}
if(area<0){
for(pair<pt, pt>&edge : edges){
edge = {edge.first+edge.second, -edge.second};
}
}
vector<Interval> inters;
for(auto e: edges){
if(e.second.imag()!=0){
if(e.second.imag()>0){
inters.push_back(Interval{e.first.real(), e.first.imag(), e.first.imag()+e.second.imag()-1, true});
}
else if(e.second.imag()<0){
inters.push_back(Interval{e.first.real(), e.first.imag()+e.second.imag(), e.first.imag()-1, false});
}
}
}
auto cmp = [&](Interval& a, Interval& b){
return a.x<b.x;
};
sort(inters.begin(), inters.end(), cmp);
vector<InterSet> inter_set(2);
int k = 0;
for(auto e: inters){
if(inter_set[0].intervals.size()==0 || inter_set[1].intervals.size()==0){
if(inter_set[0].is_valid && inter_set[1].is_valid){
k = e.x-1;
}
}
if(e.open){
inter_set[e.x%2].insert(e);
}
else{
inter_set[0].insert(e);
inter_set[1].insert(e);
}
if(inter_set[0].intervals.size()==0 || inter_set[1].intervals.size()==0){
if(inter_set[0].is_valid && inter_set[1].is_valid){
k = e.x;
}
}
}
cout<<k<<endl;
}
Compilation message
Main.cpp: In member function 'void InterSet::insert(Interval)':
Main.cpp:84:18: warning: variable 'e' set but not used [-Wunused-but-set-variable]
84 | for(auto e: intervals){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
29 ms |
3728 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 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 |
56 ms |
8556 KB |
Output is correct |
| 3 |
Correct |
57 ms |
8508 KB |
Output is correct |
| 4 |
Correct |
969 ms |
16956 KB |
Output is correct |
| 5 |
Correct |
981 ms |
17068 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Execution timed out |
2098 ms |
17068 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
16440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
