oj.uz

Submission #832766

# Submission time Handle Problem Language Result Execution time Memory
832766 2023-08-21T14:36:01 Z Jokubas Crosses on the Grid (FXCUP4_cross) C++17
100 / 100
 263 ms 32560 KB 
#include <iostream>
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;

using namespace std;

ll SelectCross (int K, vector<int> I, vector<int> O)
{
    ll ats = 0;

    int N = I.size();

    map<int, vector<int>> lol;

    vector<pair<int, int>> visi;

    for(int i = 0; i<N; i++)
    {
        visi.pb({I[i], O[i]});

        lol[I[i]].pb(O[i]);
    }

    sort(visi.begin(), visi.end());
    reverse(visi.begin(), visi.end());

    int kiek = lol.size();

    int kur = 0;
    int isviso = 0;

    //vector<int> didziausi;
    //deque<int> didziausi;

    priority_queue<int, vector<int>, greater<int>> didziausi;

    for(int i = 0; i<kiek; i++)
    {
        int dabar = visi[kur].first;

        int kiekisI = lol[dabar].size();

        isviso += kiekisI;


        for(int j = 0; j<kiekisI; j++)
        {
            didziausi.push(visi[kur + j].second);

            if(didziausi.size()>K)
            {
                didziausi.pop();
            }
        }

        /*
        int k = 0;
        int j = 0;

        while(j < K && k < kiekisI)
        {
            int db = visi[kur + k].second;

            if((int)didziausi.size() <= j)
            {
                didziausi.pb(visi[kur + k].second);
                j++; k++;
                continue;
            }


            if(db <= didziausi[min((int)didziausi.size()-1, K-1)])
            {
                j = min((int)didziausi.size()-1, K-1) + 1;
                continue;
            }


            if(db >= didziausi[j])
            {
                didziausi.insert(didziausi.begin() + j, db);
                k++; j++;
                continue;
            }






            int r = j;
            int l = min((int)didziausi.size()-1, K-1);

            bool skip = 0;
            while(r<l)
            {
                int m = (r+l)/2;

                if(db < didziausi[m])
                {
                    r = m;

                }
                if(db > didziausi[m])
                {
                    l = m;
                }
                if(db == didziausi[m])
                {
                    didziausi.insert(didziausi.begin() + j, db);
                    k++;
                    r = l+1;
                    skip = 1;

                }
            }
        }*/

        if(isviso < K)
        {
            kur = isviso;
            continue;
        }

        //ll plotas = (ll)dabar*(2*(ll)didziausi[K-1] - (ll)dabar);

        ll plotas = (ll)dabar*(2*(ll)didziausi.top() - (ll)dabar);

        ats = max(ats, plotas);


        kur = isviso;
    }


    return ats;
}

Compilation message

cross.cpp: In function 'll SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:51:32: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |             if(didziausi.size()>K)
      |                ~~~~~~~~~~~~~~~~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 8 ms 1824 KB Output is correct
6 Correct 208 ms 26856 KB Output is correct
7 Correct 221 ms 26896 KB Output is correct
8 Correct 215 ms 26836 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 8 ms 1824 KB Output is correct
6 Correct 208 ms 26856 KB Output is correct
7 Correct 221 ms 26896 KB Output is correct
8 Correct 215 ms 26836 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 1876 KB Output is correct
13 Correct 74 ms 13848 KB Output is correct
14 Correct 209 ms 26852 KB Output is correct
15 Correct 219 ms 26892 KB Output is correct
16 Correct 211 ms 27024 KB Output is correct

Subtask #3
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 8 ms 1824 KB Output is correct
6 Correct 208 ms 26856 KB Output is correct
7 Correct 221 ms 26896 KB Output is correct
8 Correct 215 ms 26836 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 7 ms 1876 KB Output is correct
13 Correct 74 ms 13848 KB Output is correct
14 Correct 209 ms 26852 KB Output is correct
15 Correct 219 ms 26892 KB Output is correct
16 Correct 211 ms 27024 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 8 ms 2132 KB Output is correct
20 Correct 92 ms 13880 KB Output is correct
21 Correct 157 ms 21316 KB Output is correct
22 Correct 244 ms 26888 KB Output is correct
23 Correct 263 ms 26852 KB Output is correct
24 Correct 216 ms 27040 KB Output is correct
25 Correct 254 ms 32324 KB Output is correct
26 Correct 210 ms 32560 KB Output is correct