Submission #771614

#	Time	Username	Problem	Language	Result	Execution time	Memory
771614		gagik_2007	New Home (APIO18_new_home)	C++17	12 / 100	5045 ms	61340 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

class Point;

class Query{
public:
    int x;
    int y;
    int ind;
    Query() : x(0), y(0) {}
    Query(int xx, int yy, int i) : x(xx), y(yy), ind(i) {}
    bool operator<(const Query& other) const {
        if(y==other.y){
            if(x==other.x)return ind<other.ind;
            return x<other.x;
        }
        return y<other.y;
    }
    bool operator<(const Point& other) const;
};

class Point {
public:
    int x;
    int t;
    int a;
    int b;
    bool is_erase;
    Point() : x(0), t(0), a(0), b(0) {}
    Point(int xx, int tt, int aa, int bb, bool er) : 
            x(xx), t(tt), a(aa), b(bb), is_erase(er) {}
    bool operator<(const Point& other) const {
        if(other.a==a){
            if(other.b==b){
                if(other.x==x){
                    return t<other.t;
                }
                return x<other.x;
            }
            return b<other.b;
        }
        return a<other.a;
    }
    bool operator<(const Query& other) const {
        return a<=other.y;
    }
};

bool Query::operator<(const Point& other) const {
    return this->y<other.a;
}

class Node {
public:
    Query q;
    Point p;
    bool is_q;
    Node(Query qq) : q(qq) {
        is_q=true;
    }
    Node(Point pp) : p(pp) {
        is_q=false;
    }
    bool operator<(const Node& other) const {
        if(is_q && other.is_q)return q<other.q;
        if(is_q) return q<other.p;
        if(other.is_q) return p<other.q;
        return p<other.p;
    }
};

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
ll n,m,k;
multiset<int>d[N];
vector<Node>s;

int calc_ans(int x){
    int ans=0;
    for(int i=1;i<=k;i++){
        if(d[i].size()==0)return -1;
        auto it=d[i].lower_bound(x);
        int fd=MOD,sd=MOD;
        if(it!=d[i].end()){
            fd=*it-x;
        }
        if(it!=d[i].begin()){
            it--;
            sd=x-*it;
        }
        ans=max(ans,min(fd,sd));
    }
    return ans;
}

int main() {
    cin>>n>>k>>m;
    for(int i=0;i<n;i++){
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        s.push_back(Node(Point(x,t,a,b,false)));
        s.push_back(Node(Point(x,t,b+1,b,true)));
    }
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        s.push_back(Node(Query(x,y,i)));
    }
    sort(s.begin(),s.end());
    vector<int>ans(m,-1);
    for(int i=0;i<s.size();i++){
        if(s[i].is_q){
            ans[s[i].q.ind] = calc_ans(s[i].q.x);
        }
        else{
            if(s[i].p.is_erase){
                d[s[i].p.t].erase(d[s[i].p.t].find(s[i].p.x));
            }
            else{
                d[s[i].p.t].insert(s[i].p.x);
            }
        }
    }
    for(int x:ans)cout<<x<<"\n";
    cout<<endl;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20