Submission #710668

#	Time	Username	Problem	Language	Result	Execution time	Memory
710668		lam	New Home (APIO18_new_home)	C++14	33 / 100	2240 ms	103888 KiB

new_home

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
typedef pair<ii,ii> iiii;
#define ff first
#define ss second
const int maxn = 3e5+10;
int n,k,m,o;
map<int,int> mp;
int b[maxn];
vector <iiii> d;
ii f[4*maxn];
multiset<int> ms[maxn];
int res[maxn];
int calc(ii x, int y)
{
    return x.ff*y+x.ss;
}
void update2(int x, int lx, int rx, ii line)
{
    if (lx==rx)
    {
        if (calc(line,b[lx]) > calc(f[x],b[lx])) swap(line,f[x]);
        return;
    }
    int mid=(lx+rx)/2;
    if (calc(line,b[mid]) > calc(f[x],b[mid])) swap(line,f[x]);
    if (calc(line,b[lx]) > calc(f[x],b[lx])) update2(2*x,lx,mid,line);
    else update2(2*x+1,mid+1,rx,line);
}

void update(int x, int lx, int rx, int l, int r, ii line)
{
//    if (x==1) cout<<"+ "<<l<<' '<<r<<" = "<<line.ff<<','<<line.ss<<endl;
    if (b[lx]>r||b[rx]<l) return;
    if (b[lx]>=l&&b[rx]<=r)
    {
        update2(x,lx,rx,line);
        return;
    }
    int mid=(lx+rx)/2;
    update(2*x,lx,mid,l,r,line);
    update(2*x+1,mid+1,rx,l,r,line);
}
int get(int x, int lx, int rx, int idx)
{
    if (lx==rx) return calc(f[x],b[idx]);
    int mid=(lx+rx)/2;
    if (idx<=mid) return max(calc(f[x],b[idx]),get(2*x,lx,mid,idx));
    else return max(calc(f[x],b[idx]),get(2*x+1,mid+1,rx,idx));
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>k>>m;
    int cnt = 0;
    for (int i=1; i<=n; i++)
    {
        int x,t,l,r; cin>>x>>t>>l>>r;
        if (ms[t].empty()) cnt++;
        ms[t].insert(x);
        d.push_back({{r,1},{x,t}});
    }
    for (int i=1; i<=m; i++)
    {
        int x,t; cin>>x>>t;
        d.push_back({{t,0},{x,i}});
        mp[x] = 1;
    }
    o=0;
    for (auto &c:mp) c.ss = ++o, b[o] = c.ff;
    sort(d.begin(),d.end());
    if (cnt!=k)
    {
        for (int i=1; i<=m; i++) cout<<"-1\n";
        return 0;
    }
    for (int i=1; i<=k; i++)
    {
        auto j = ms[i].begin();
        int id = upper_bound(b+1,b+o+1,(*j)) - b - 1;
//        cout<<i<<" -> "<<(*j)<<endl;
        update(1,1,o,1,(*j),{-1,(*j)});
        while (true)
        {
            auto j2 = j; j2++;
            if (j2 == ms[i].end())
            {
                id = lower_bound(b+1,b+o+1,(*j)) - b;
                update(1,1,o,(*j),b[o],{1,-(*j)});
                break;
            }
            int l = (*j); int r = (*j2);
            j = j2;
            int mid = (l+r)/2;
            update(1,1,o,l,mid,{1,-l});
            update(1,1,o,mid+1,r,{-1,r});
        }
    }
    for (iiii i:d)
    {
        if (i.ff.ss == 1)
        {
            if (cnt<k) continue;
            int x = i.ss.ff; int t = i.ss.ss;
            auto j = ms[t].lower_bound(x);
            auto r = j; auto l = j;
            r++;
            if (l!=ms[t].begin())
            {
                l--;
                if (r!=ms[t].end())
                {
                    int ll = (*l); int rr = (*r);
                    int mid = (ll+rr)/2;
                    update(1,1,o,ll,mid,{1,-ll});
                    update(1,1,o,mid+1,rr,{-1,rr});
                }
                else update(1,1,o,(*l),b[o],{1,-(*l)});
            }
            else
            {
                if (r!=ms[t].end())
                {
                    update(1,1,o,1,(*r),{-1,(*r)});
                }
                else cnt--;
            }
            ms[t].erase(ms[t].find(x));
        }
        else
        {
            int x = i.ss.ff; int id = i.ss.ss;
            if (cnt<k) res[id] = -1;
            else {
                int j = lower_bound(b+1,b+o+1,x) - b;
                res[id] = get(1,1,o,j);
            }
        }
    }
    for (int i=1; i<=m; i++) cout<<res[i]<<'\n';
}
/**
4 2 4
3 1 1 10
9 2 1 7
7 2 1 4
4 1 1 10
5 3
5 5
5 8
1 4
**/

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:84:13: warning: variable 'id' set but not used [-Wunused-but-set-variable]
   84 |         int id = upper_bound(b+1,b+o+1,(*j)) - b - 1;
      |             ^~

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