Submission #774424

#	Time	Username	Problem	Language	Result	Execution time	Memory
774424		gagik_2007	New Home (APIO18_new_home)	C++17	0 / 100	3887 ms	1048576 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;

#define ff first
#define ss second

class Line{
public:
    int l,r;
    int a,b;
    Line() : l(0), r(0), a(0), b(0) {}
    Line(int lll, int rr, int aa, int bb) : l(lll), r(rr), a(aa), b(bb) {}
    bool operator<(const Line& other)const{
        if(l==other.l){
            if(r==other.r){
                if(a==other.a){
                    return b<other.b;
                }
                return a<other.a;
            }
            return r<other.r;
        }
        return l<other.l;
    }
};

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

ll ttt;
const ll INF=1e18;
const int MOD=1e9+7;
const ll N=1e6+7;
ll n,m,k;
set<Line>s[N];
vector<Point>d[N];
vector<Point>ps;
int ps_cnt[N];
vector<pair<int,bool>>pss;
vector<Line>ls[N];
vector<pair<Line, bool>>p[N];
vector<int>times;
unordered_map<int,int>compress;
vector<pair<int,int>>t1[4*N],t2[4*N];
vector<int>pf1[4*N],pf2[4*N];
vector<pair<int,int>>qs;

void update1(int v, int tl, int tr, int l, int r, pair<int,int> vl){
    if(l>r)return;
    if(tl==l&&tr==r){
        t1[v].push_back(vl);
    }
    else{
        int tm=(tl+tr)/2;
        update1(2*v,tl,tm,l,min(r,tm),vl);
        update1(2*v+1,tm+1,tr,max(l,tm+1),r,vl);
    }
}

void update2(int v, int tl, int tr, int l, int r, pair<int,int> vl){
    if(l>r)return;
    if(tl==l&&tr==r){
        t2[v].push_back({vl.ss,vl.ff});
    }
    else{
        int tm=(tl+tr)/2;
        update2(2*v,tl,tm,l,min(r,tm),vl);
        update2(2*v+1,tm+1,tr,max(l,tm+1),r,vl);
    }
}

void tpel(int v, int tl, int tr){
    // cout<<"["<<times[tl]<<", "<<times[tr]<<"]: ";
    // for(pii&x:t1[v]){
    //     // cout<<"("<<x.ff<<", "<<x.ss<<"), ";

    // }
    // cout<<endl;
    if(t1[v].size()){
        pf1[v].push_back(t1[v][0].ss);
        for(int i=1;i<t1[v].size();i++){
            pf1[v].push_back(max(pf1[v].back(),t1[v][i].ss));
        }
    }
    if(t2[v].size()){
        pf2[v].push_back(t2[v][0].ss);
        for(int i=1;i<t2[v].size();i++){
            pf2[v].push_back(min(pf2[v].back(),t2[v][i].ss));
        }
    }
    if(tl!=tr){
        int tm=(tl+tr)/2;
        tpel(2*v,tl,tm);
        tpel(2*v+1,tm+1,tr);
    }
}

int query1(int v, int tl, int tr, int x, int t){
    auto it=upper_bound(t1[v].begin(),t1[v].end(),make_pair(x,MOD));
    int cur=0;
    if(it!=t1[v].begin()){
        it--;
        int ind=it-t1[v].begin();
        cur=pf1[v][ind];
    }
    if(tl!=tr){
        int tm=(tl+tr)/2;
        if(tm>=t)cur=max(cur,query1(2*v,tl,tm,x,t));
        else cur=max(cur,query1(2*v+1,tm+1,tr,x,t));
    }
    return cur;
}

int query2(int v, int tl, int tr, int x, int t){
    auto it=upper_bound(t2[v].begin(),t2[v].end(),make_pair(x,MOD));
    int cur=MOD;
    if(it!=t2[v].begin()){
        it--;
        int ind=it-t2[v].begin();
        cur=pf2[v][ind];
    }
    if(tl!=tr){
        int tm=(tl+tr)/2;
        if(tm>=t)cur=min(cur,query2(2*v,tl,tm,x,t));
        else cur=min(cur,query2(2*v+1,tm+1,tr,x,t));
    }
    return cur;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("output.txt","w",stdout);
    cin>>n>>k>>m;
    for(int c=1;c<=k;c++){
        s[c].insert(Line(0,1e8+1,0,0));
    }
    for(int i=0;i<n;i++){
        int x,t,a,b;
        cin>>x>>t>>a>>b;
        d[t].push_back(Point(x,t,a,b,false));
        d[t].push_back(Point(x,t,b,b,true));
        ps.push_back(Point(x,t,a,b,false));
        ps.push_back(Point(x,t,b+1,b,true));
    }
    sort(ps.begin(),ps.end());
    set<int>baner;
    for(int i=1;i<=k;i++)baner.insert(i);
    for(Point&pp:ps){
        if(pp.helnox){
            ps_cnt[pp.t]--;
            if(ps_cnt[pp.t]==0){
                baner.insert(pp.t);
            }
        }
        else{
            if(ps_cnt[pp.t]==0){
                baner.erase(pp.t);
            }
            ps_cnt[pp.t]++;
        }
        pss.push_back({pp.a,baner.size()!=0});
        // cout<<pp.a<<" "<<(baner.size()!=0)<<endl;
    }
    for(int c=1;c<=k;c++){
        sort(d[c].begin(),d[c].end());
        for(int i=0;i<d[c].size();i++){
            if(!d[c][i].helnox){
                auto it=s[c].upper_bound(Line(d[c][i].x,MOD,MOD,MOD));
                it--;
                Line x=*it;
                x.b=d[c][i].a-1;
                ls[c].push_back(x);
                Line fst((*it).l,d[c][i].x,d[c][i].a,0);
                Line snd(d[c][i].x,(*it).r,d[c][i].a,0);
                s[c].erase(it);
                s[c].insert(fst);
                s[c].insert(snd);
            }
            else{
                auto it=s[c].lower_bound(Line(d[c][i].x,0,0,0));
                auto it2=it;
                it2--;
                Line fst=*it2;
                fst.b=d[c][i].a;
                ls[c].push_back(fst);
                Line snd=*it;
                snd.b=d[c][i].a;
                ls[c].push_back(snd);
                Line x(fst.l,snd.r,d[c][i].a+1,0);
                s[c].erase(it);
                s[c].erase(it2);
                s[c].insert(x);
            }
        }
        for(int i=0;i<ls[c].size();i++){
            if(ls[c][i].l!=0&&ls[c][i].r!=1e8+1){
                int mid=(ls[c][i].l+ls[c][i].r)/2;
                p[c].push_back({Line(ls[c][i].l,mid,ls[c][i].a,ls[c][i].b),false});
                p[c].push_back({Line(mid+1,ls[c][i].r,ls[c][i].a,ls[c][i].b),true});
            }
            else if(ls[c][i].l==0){
                Line x=ls[c][i];
                x.l=1;
                p[c].push_back({x,true});
            }
            else{
                Line x=ls[c][i];
                x.r=1e8;
                p[c].push_back({x,false});
            }
        }
        // cout<<c<<":\n";
        // cout<<"ls\n";
        // for(Line& x:ls[c]){
        //     cout<<"["<<x.l<<", "<<x.r<<"] -> ("
        //         <<x.a<<", "<<x.b<<")"<<endl;
        // }
        // cout<<"p\n";
        // for(int i=0;i<p[c].size();i++){
        //     cout<<"["<<p[c][i].first.l<<", "<<p[c][i].first.r<<"] -> ("
        //         <<p[c][i].first.a<<", "<<p[c][i].first.b<<"), "<<p[c][i].second<<endl;
        // }
        for(pair<Line,bool>& x:p[c]){
            times.push_back(x.ff.a);
            times.push_back(x.ff.b);
        }
    }
    for(int i=0;i<m;i++){
        int x,t;
        cin>>x>>t;
        times.push_back(t);
        qs.push_back({x,t});
    }
    sort(times.begin(),times.end());
    auto it=unique(times.begin(),times.end());
    times.resize(it-times.begin());
    for(int i=0;i<times.size();i++){
        compress[times[i]]=i;
    }
    n=times.size();
    for(int c=1;c<=k;c++){
        for(pair<Line,bool>&x:p[c]){
            if(x.ff.r>=x.ff.l&&x.ff.a!=0&&x.ff.b!=1e8+1&&x.ff.a<=x.ff.b){
                if(x.ss){
                    update1(1,0,n-1,compress[x.ff.a],compress[x.ff.b],{x.ff.l,x.ff.r});
                }
                else{
                    update2(1,0,n-1,compress[x.ff.a],compress[x.ff.b],{x.ff.l,x.ff.r});
                }
                // cout<<"QUERY: "<<1<<" "<<0<<" "<<n-1<<" "<<x.ff.a<<
                //     " "<<x.ff.b<<" {"<<x.ff.l<<", "<<x.ff.r<<"}\n";
            }
        }
    }
    for(int v=1;v<=4*n;v++){
        sort(t1[v].begin(),t1[v].end());
        sort(t2[v].begin(),t2[v].end());
    }
    // cout<<"t1:\n";
    // tpel1(1,0,n-1);
    // cout<<endl<<"t2:\n";
    // tpel2(1,0,n-1);
    tpel(1,0,n-1);
    // for(int v=1;v<=4*n;v++){
    //     for(auto x:t1[v]){
    //         cout<<x.ff<<" "<<x.ss<<"\t";
    //     }
    //     cout<<endl;
    // }
    for(int i=0;i<qs.size();i++){
        int t=qs[i].ss;
        int x=qs[i].ff;
        // cout<<t<<endl;
        auto it=upper_bound(pss.begin(),pss.end(),make_pair(t,true));
        if(it==pss.begin()){
            cout<<-1<<endl;
            continue;
        }
        it--;
        if((*it).ss){
            cout<<-1<<endl;
            continue;
        }
        int r=query1(1,0,n-1,x,compress[t]);
        int l=query2(1,0,n-1,x,compress[t]);
        cout<<max(x-l,r-x)<<endl;
    }
}

Compilation message (stderr)

new_home.cpp: In function 'void tpel(int, int, int)':
new_home.cpp:102:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i=1;i<t1[v].size();i++){
      |                     ~^~~~~~~~~~~~~
new_home.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int i=1;i<t2[v].size();i++){
      |                     ~^~~~~~~~~~~~~
new_home.cpp: In function 'int main()':
new_home.cpp:189:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         for(int i=0;i<d[c].size();i++){
      |                     ~^~~~~~~~~~~~
new_home.cpp:218:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |         for(int i=0;i<ls[c].size();i++){
      |                     ~^~~~~~~~~~~~~
new_home.cpp:260:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  260 |     for(int i=0;i<times.size();i++){
      |                 ~^~~~~~~~~~~~~
new_home.cpp:293:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  293 |     for(int i=0;i<qs.size();i++){
      |                 ~^~~~~~~~~~

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