oj.uz

Submission #150741

# Submission time Handle Problem Language Result Execution time Memory
150741 2019-09-01T08:52:57 Z (παρα)γεμιστά(#3619, cfalas, ctziapo, Charis02) Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 932 ms 50024 KB 
#include "cross.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define ll long long
#define pi pair < ll,ll >
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 2000004

using namespace std;

pi ar[MAXN];
ll seg[4*MAXN];
unordered_map < ll,ll > mapper;
unordered_map < ll,ll > inverse;
ll cnt = 1;

void update(ll low,ll high,ll pos,ll slow)
{
    if(low == high && low == slow)
    {
        seg[pos]++;
        return;
    }
    if(low > slow || high < slow)
        return;

    ll mid = (low+high)/2;

    update(low,mid,pos*2+1,slow);
    update(mid+1,high,pos*2+2,slow);

    seg[pos] = seg[pos*2+1]+seg[pos*2+2];
    return;
}

ll query(ll low,ll high,ll pos,ll val)
{
    ll mid = (low+high)/2;

    if(low == high)
        return low;


    if(seg[pos*2+2] >= val)
        return query(mid+1,high,pos*2+2,val);
    else
        return query(low,mid,pos*2+1,val-seg[pos*2+2]);
}

ll findclosestright(ll low,ll high,ll pos,ll slow)
{
    if(seg[pos] == 0)
        return MAXN;

    ll mid= (low+high)/2;

    if(low > slow)
    {
        if(low == high)
            return low;
        else if(seg[pos*2+1] > 0)
            return findclosestright(low,mid,pos*2+1,slow);
        else
            return findclosestright(mid+1,high,pos*2+2,slow);
    }
    if(high <= slow)
        return MAXN;

    return min(findclosestright(low,mid,pos*2+1,slow),findclosestright(mid+1,high,pos*2+2,slow));
}

ll findclosestleft(ll low,ll high,ll pos,ll shigh)
{
    if(seg[pos] == 0)
        return MAXN;

    ll mid= (low+high)/2;

    if(high <= shigh)
    {
        if(low == high)
            return low;
        else if(seg[pos*2+2] > 0)
            return findclosestleft(mid+1,high,pos*2+2,shigh);
        else
            return findclosestleft(low,mid,pos*2+1,shigh);
    }
    if(low > shigh)
        return -1;

    return max(findclosestleft(low,mid,pos*2+1,shigh),findclosestleft(mid+1,high,pos*2+2,shigh));
}

long long SelectCross(int K, std::vector<int> I, std::vector<int> O) {
	int n = I.size();

    vector < ll > v;
	ll ans =0;

	rep(i,0,n)
    {
        ar[i].first = -O[i]*1LL;
        ar[i].second = I[i]*1LL;

        v.push_back(I[i]);
        v.push_back(O[i]);
    }

    sort(v.begin(),v.end());

    rep(i,0,v.size())
    {
        if(!mapper[v[i]])
        {
            mapper[v[i]]= cnt;
            inverse[cnt] = v[i];
            cnt++;
        }
    }

    sort(ar,ar+n);

    rep(i,0,n)
    {
        ar[i].first*=-1;
        update(0,cnt,0,mapper[ar[i].second]);
        ll peaki = mapper[ar[i].first];
        ll epilogi = 0;

        if(seg[0] >= K)
        {
            ll maxim = query(0,cnt,0,K);
            ll cand2 = findclosestright(0,cnt,0,peaki);
            ll cand1 = findclosestleft(0,cnt,0,peaki);

            if(cand1 == -1)
                cand1 = cand2;
            else if(cand2 == MAXN)
                cand2 = cand1;

            if(cand1 > maxim)
                epilogi = maxim;
            else if(cand1 != -1 && cand2 > maxim)
                epilogi = cand1;
            else if(2*ar[i].first*inverse[cand1] - inverse[cand1]*inverse[cand1] <= 2*ar[i].first*inverse[cand2] - inverse[cand2]*inverse[cand2])
                epilogi = cand2;
            else
                epilogi = cand1;

            epilogi = inverse[epilogi];

            ans = max(ans,2*ar[i].first*epilogi - epilogi*epilogi);
        }
    }

	return ans;
}

Compilation message

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:8:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i = a;i < b;i++)
cross.cpp:113:9:
     rep(i,0,v.size())
         ~~~~~~~~~~~~                
cross.cpp:113:5: note: in expansion of macro 'rep'
     rep(i,0,v.size())
     ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 34 ms 3452 KB Output is correct
6 Correct 839 ms 50020 KB Output is correct
7 Correct 769 ms 50020 KB Output is correct
8 Correct 813 ms 50016 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 34 ms 3452 KB Output is correct
6 Correct 839 ms 50020 KB Output is correct
7 Correct 769 ms 50020 KB Output is correct
8 Correct 813 ms 50016 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 33 ms 3440 KB Output is correct
13 Correct 387 ms 25448 KB Output is correct
14 Correct 791 ms 49892 KB Output is correct
15 Correct 932 ms 50016 KB Output is correct
16 Correct 865 ms 50004 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 34 ms 3452 KB Output is correct
6 Correct 839 ms 50020 KB Output is correct
7 Correct 769 ms 50020 KB Output is correct
8 Correct 813 ms 50016 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 6 ms 384 KB Output is correct
11 Correct 7 ms 640 KB Output is correct
12 Correct 33 ms 3440 KB Output is correct
13 Correct 387 ms 25448 KB Output is correct
14 Correct 791 ms 49892 KB Output is correct
15 Correct 932 ms 50016 KB Output is correct
16 Correct 865 ms 50004 KB Output is correct
17 Correct 6 ms 384 KB Output is correct
18 Correct 8 ms 640 KB Output is correct
19 Correct 33 ms 3580 KB Output is correct
20 Correct 357 ms 25568 KB Output is correct
21 Correct 662 ms 42592 KB Output is correct
22 Correct 797 ms 50016 KB Output is correct
23 Correct 841 ms 50004 KB Output is correct
24 Correct 766 ms 50016 KB Output is correct
25 Correct 650 ms 50024 KB Output is correct
26 Correct 567 ms 50020 KB Output is correct