oj.uz

Submission #710668

# Submission time Handle Problem Language Result Execution time Memory
710668 2023-03-15T14:39:31 Z lam New Home (APIO18_new_home) C++14
33 / 100
 2240 ms 103888 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14436 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14436 KB Output is correct
4 Incorrect 8 ms 14420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14436 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14436 KB Output is correct
4 Incorrect 8 ms 14420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 98568 KB Output is correct
2 Correct 1159 ms 101184 KB Output is correct
3 Correct 1310 ms 103888 KB Output is correct
4 Correct 1526 ms 103540 KB Output is correct
5 Correct 1028 ms 100796 KB Output is correct
6 Correct 1105 ms 101104 KB Output is correct
7 Correct 1178 ms 103752 KB Output is correct
8 Correct 1315 ms 103476 KB Output is correct
9 Correct 1471 ms 103452 KB Output is correct
10 Correct 1291 ms 102272 KB Output is correct
11 Correct 774 ms 101048 KB Output is correct
12 Correct 953 ms 102260 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2240 ms 98276 KB Output is correct
2 Correct 392 ms 65428 KB Output is correct
3 Correct 1580 ms 101176 KB Output is correct
4 Correct 1241 ms 101604 KB Output is correct
5 Correct 1380 ms 101508 KB Output is correct
6 Correct 1395 ms 101440 KB Output is correct
7 Correct 1410 ms 100644 KB Output is correct
8 Correct 1550 ms 101076 KB Output is correct
9 Correct 1152 ms 102956 KB Output is correct
10 Correct 1723 ms 102684 KB Output is correct
11 Correct 2098 ms 102920 KB Output is correct
12 Correct 1709 ms 101868 KB Output is correct
13 Correct 720 ms 99940 KB Output is correct
14 Correct 713 ms 99316 KB Output is correct
15 Correct 829 ms 100676 KB Output is correct
16 Correct 1130 ms 101768 KB Output is correct
17 Correct 884 ms 100232 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14436 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14436 KB Output is correct
4 Incorrect 8 ms 14420 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14436 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 8 ms 14436 KB Output is correct
4 Incorrect 8 ms 14420 KB Output isn't correct
5 Halted 0 ms 0 KB -