// sub 4
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<cassert>
#include<cstdio>
#include<vector>
#include<cstdint>
#include<climits>
#include<array>
#include<algorithm>
#include<set>
struct Input{
int get(){return std::getchar();}
/*
auto& operator>>(std::string& it){
it.clear();
char ch;
do{
while((ch=(char)get())>' ') it+=ch;
}while(it.empty());
return *this;
}
*/
auto& ignore(std::size_t number){
while(number--) get();
return *this;
}
auto& operator>>(char& it){
while((it=(char)get())<=' ') {}
return *this;
}
template<class T, class=std::enable_if<std::is_integral<T>::value>>
auto& operator>>(T& it){
while((it=get())<'0') {}
it-='0';
int ch; while((ch=get())>='0') it=it*10+ch-'0';
return *this;
}
} cin;
struct Output{
auto& operator<<(char it) {
std::putchar(it); return *this;
}
auto& operator<<(int it) {
std::printf("%d", it); return *this;
}
auto& operator<<(char const* it) {
for(; *it; ++it) std::putchar(*it);
return *this;
}
} cout;
// remark about precompiled headers and compile time: #include<string> or #include<iostream> adds about 0.5s to the compilation time, even with precompiled header.
// ...
//
// libraries are either too long (some sites allow less than Codeforces...) or not having enough functionality.
// A problem with competitive programming and single-file solution...
int constexpr maxQueryPosition=
#ifdef LOCAL
//10
100000001
#else
100000001
#endif
;
struct Tree{
struct Node{
int left, right; // 0: not yet created
int value;
};
std::vector<Node> data;
Tree(): data(1, {0, 0, INT_MIN}){}
int get(int index,
int node=0, int left=0, int right=maxQueryPosition, int result=INT_MIN){
int const mid=(left+right)>>1;
assert(left<=index); assert(index<right);
result=std::max(result, data[node].value);
if(index<mid){
if(auto const child=data[node].left) return get(index, child, left, mid, result);
}else{
if(auto const child=data[node].right) return get(index, child, mid, right, result);
}
return result;
}
void change(int changeLeft, int changeRight, int value,
int node=0, int left=0, int right=maxQueryPosition){
assert(changeRight<=maxQueryPosition);
assert(not(changeLeft>=right or changeRight<=left));
if(changeLeft<=left and right<=changeRight){
data[node].value=std::max(data[node].value, value);
return;
}
int const mid=(left+right)>>1;
if(changeLeft<mid){
auto& child=data[node].left;
int child1=child; // data.push_back invalidates child
if(child==0){child=child1=(int)data.size(); data.push_back({0, 0, INT_MIN});}
change(changeLeft, changeRight, value, child1, left, mid);
}
if(changeRight>mid){
auto& child=data[node].right;
int child1=child;
if(child==0){child=child1=(int)data.size(); data.push_back({0, 0, INT_MIN});}
change(changeLeft, changeRight, value, child1, mid, right);
}
}
};
int main(){
/*
{
Tree tree;
tree.change(2, 5, 4);
cout<<tree.get(2)<<'\n';
return 0;
}
*/
int numStore, numType, numQuery; cin>>numStore>>numType>>numQuery;
struct Event{
int position, time;
int data; // shopType or queryIndex
enum class Type{
open, close, query
};
Type type;
bool operator<(Event it)const{
//check(); it.check();
return time!=it.time ? time<it.time: type<it.type;
} // query after open/close if same time
};
std::vector<Event> events; events.reserve(numStore*2+numQuery);
for(int _=0; _<numStore; ++_){
int position, type, open, close; cin>>position>>type>>open>>close;
assert(1<=type and type<=numType); --type;
if(open!=1) return 1;
events.push_back({position, open, type, Event::Type::open});
events.push_back({position, close+1, type, Event::Type::close});
}
for(int queryIndex=0; queryIndex<numQuery; ++queryIndex){
int position, time; cin>>position>>time;
assert(0<=position); assert(position<maxQueryPosition);
events.push_back({position, time, queryIndex, Event::Type::query});
}
std::sort(begin(events), end(events));
// a map<int, int> would work too
std::vector<std::multiset<int>> positions(numType);
auto iterator=events.begin();
while(iterator!=events.end() and iterator->type==Event::Type::open){
auto const [position, time, data, type]=*iterator;
++iterator;
assert(type==Event::Type::open);
positions[data].insert(position);
}
/*
struct Tree{
std::vector<int> data;
Tree(): data(maxQueryPosition, INT_MIN){}
int get(int index){
return data[index];
}
void change(int left, int right, int value){
for(int i=left; i<right; ++i) data[i]=std::max(data[i], value);
}
};
*/
Tree up, down;
bool possible=true;
auto const getResult=[&](int position){
if(not possible) return -1;
return std::max(up.get(position)+position, down.get(position)-position);
};
auto const changeSegment=[&](int last, int position){
auto const mid=(last+position)/2;
up.change(last, mid, -last);
down.change(mid, position, position);
};
auto const changePrefix=[&](int position){
down.change(0, position, position);
};
auto const changeSuffix=[&](int last){
up.change(last, maxQueryPosition, -last);
};
for(auto const& it: positions){
if(it.empty()){ possible=false; break; }
int last=-1;
for(auto position: it){
if(position==last) continue;
if(last<0){
assert(last==-1);
// [..position]
changePrefix(position);
}else{
// [last..position]
changeSegment(last, position);
}
last=position;
}
// [last..]
changeSuffix(last);
}
std::vector<int> result(numQuery);
for(; iterator!=events.end();++iterator){
auto const [position, time, data, type]=*iterator;
switch(type){
case Event::Type::open:
assert(false); __builtin_unreachable();
case Event::Type::close:
{
auto const shopType=data;
auto const nextIterator=positions[shopType].erase(positions[shopType].find(position));
bool const havePrevious=nextIterator!=positions[shopType].begin();
bool const haveNext=nextIterator!=positions[shopType].end();
int previous; if(havePrevious) previous=*std::prev(nextIterator);
int next; if(haveNext) next=*nextIterator;
if((havePrevious and previous==position) or (haveNext and next==position))
break; // nothing changes.
if(havePrevious and haveNext){
changeSegment(previous, next);
}else if(havePrevious){
changeSuffix(previous);
}else if(haveNext){
changePrefix(next);
}else{
possible=false;
}
}
break;
case Event::Type::query:
result[data]=getResult(position);
break;
}
}
for(auto it: result) cout<<it<<'\n';
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:172:41: warning: unused variable 'time' [-Wunused-variable]
auto const [position, time, data, type]=*iterator;
^
new_home.cpp:172:41: warning: unused variable 'type' [-Wunused-variable]
new_home.cpp:236:41: warning: unused variable 'time' [-Wunused-variable]
auto const [position, time, data, type]=*iterator;
^
new_home.cpp:208:12: warning: 'previous' may be used uninitialized in this function [-Wmaybe-uninitialized]
up.change(last, maxQueryPosition, -last);
~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2651 ms |
196880 KB |
Output is correct |
| 2 |
Incorrect |
2778 ms |
237724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3441 ms |
230560 KB |
Output is correct |
| 2 |
Incorrect |
412 ms |
34940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
