| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 248782 | user202729 | New Home (APIO18_new_home) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include</tmp/all.h>
struct Tree{
std::vector<int> data;
void reset(int number, int value){
data.assign(number*2, value);
}
void changeMaximum(int left, int right, int value){
left+=int(data.size()/2);
right+=int(data.size()/2);
while(left<right){
if(left&1) { data[left]=std::max(data[left], value);++left;}
if(right&1){ --right; data[right]=std::max(data[right], value);}
left>>=1; right>>=1;
}
}
int get(int index){
index+=int(data.size()/2);
int result=INT_MIN;
for(; index; index>>=1)
result=std::max(result, data[index]);
return result;
}
};
int main(){
int numStore, numType, numQuery; cin>>numStore>>numType>>numQuery;
struct Event{
int position, time, type;
bool open;
//bool operator<(Event other) const{return time<other.time;}
};
std::vector<Event> events; events.reserve(numStore*2);
for(int _=0; _<numStore; ++_){ // event before query if same time
int position, type, open, close; cin>>position>>type>>open>>close;
--type; assert(0<=type); assert(type<numType);
events.push_back({position, open, type, true});
events.push_back({position, close+1, type, false});
}
assert((int)events.size()==numStore*2);
std::sort(begin(events), end(events),[&](auto first, auto sec){return first.time<sec.time;});
struct Query{
int position, time, index;
bool operator<(Query other) const{return position<other.position;}
};
std::vector<Query> queries(numQuery);
int numTime;
{ // read queries & compress time
std::vector<int> times; times.reserve(numQuery);
for(int index=0; index<numQuery; ++index){
auto& [position, time, index_]=queries[index];
index_=index;
cin>>position>>time;
times.push_back(time);
}
std::sort(begin(queries), end(queries));
std::sort(begin(times), end(times));
times.resize(std::unique(begin(times), end(times))-begin(times));
numTime=(int)times.size();
for(auto& [_, time,__]: queries) time=int(std::lower_bound(begin(times), end(times), time)-begin(times));
for(auto& event: events) event.time=int(std::lower_bound(begin(times), end(times), event.time)-begin(times));
times.clear();
}
int const INFINITY=(int)4e8; //...
struct Event1{
int start; // inclusive (change event before query)
bool operator<(Event1 other) const{return start<other.start;}
int value; // or query index
int left, right; // half inclusive. In this problem they're time. Useless for queries
};
std::array<std::vector<Event1>, 2> events1; // [0]: increasing,[1]: decreasing
auto const addSegment=[&](int last, int time, int left, int right){
assert(left<right);
assert(last<=time); if(last==time) return;
//assert((cout<<last<<' '<<time<<' '<<left<<' '<<right<<'\n', true));
int const mid=(left+right)>>1;
events1[0].push_back({mid, -left, last, time});
events1[1].push_back({mid+1, right, last, time});
};
{ // construct events1
struct Item{
int nextLastChange;
int count;
};
std::vector<std::map<int, Item>> positions(numType);
for(auto& it: positions){ it.insert({-INFINITY, {0, 1}}); it.insert({INFINITY, {INT_MAX, 1}}); }
// ^ I should have figured out this trick earlier...
for(auto [position, time, type, open]: events){
auto& map=positions[type];
if(open){
auto [iterator, inserted]=map.insert({position, {time, 1}});
if(not inserted){ iterator->second.count++; continue; }
auto const prevIterator=std::prev(iterator);
auto const next=std::next(iterator)->first, previous=prevIterator->first;
addSegment(prevIterator->second.nextLastChange, time, previous, next);
// ^ if previous==-INFINITY and next==INFINITY then tree.get will be rather large
prevIterator->second.nextLastChange=time;
assert(iterator->second.nextLastChange==time);
}else{
auto iterator=map.find(position); --iterator->second.count;
if(iterator->second.count!=0) continue;
auto const rightLastChange=iterator->second.nextLastChange;
auto const nextIterator=map.erase(iterator), prevIterator=std::prev(nextIterator);
auto const next=nextIterator->first; auto const previous=prevIterator->first;
addSegment(prevIterator->second.nextLastChange, time, previous, position);
addSegment(rightLastChange, time, position, next);
prevIterator->second.nextLastChange=time;
}
}
int tmp=INT_MAX;
for(auto& it: positions){
assert(it.size()==2);
assert(it.begin()->first==-INFINITY);
assert(it.rbegin()->first==INFINITY);
tmp=std::min(tmp, it.begin()->second.nextLastChange);
}
addSegment(tmp, numTime,-INFINITY, INFINITY);
}
// will be processed in reverse order
std::sort(begin(events1[0]), end(events1[0]));
std::sort(begin(events1[1]), end(events1[1]), [&](Event1 first, Event1 sec){return sec<first;});
std::vector<int> result(numQuery, -1); // corresponds to the current index of queries
Tree tree;
tree.reset(numTime, -INFINITY);
{ // process events1[0]
for(auto index=numQuery; index--;){
Query query=queries[index];
while(not events1[0].empty()){
auto [start, value, left, right]=events1[0].back();
if(start<query.position) break;
tree.changeMaximum(left, right, value);
events1[0].pop_back();
}
//assert(tree.get(query.time)==-INFINITY or tree.get(query.time)+query.position>=0);
result[index]=std::max(result[index], tree.get(query.time)+query.position);
}
}
tree.reset(numTime, -INFINITY);
{ // process events1[1]
for(int index=0; index<numQuery; ++index){
Query query=queries[index];
while(not events1[1].empty()){
auto [start, value, left, right]=events1[1].back();
if(start>query.position) break;
tree.changeMaximum(left, right, value);
events1[1].pop_back();
}
//assert(tree.get(query.time)==-INFINITY or tree.get(query.time)-query.position>=0);
result[index]=std::max(result[index], tree.get(query.time)-query.position);
}
}
std::vector<int> result2(numQuery);
for(int index=0; index<numQuery; ++index){
result2[queries[index].index]=result[index];
}
for(auto cur: result2){
assert(cur!=-1); if(cur>=INFINITY/2) cur=-1;
cout<<cur<<'\n';
}
}