Submission #970764

#	Time	Username	Problem	Language	Result	Execution time	Memory
970764		vjudge1	New Home (APIO18_new_home)	C++17	0 / 100	210 ms	45736 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define ss second
#define ff first

signed main()
{
    //cout<<"hgahwg";
    int t1,t2,t3,t4;
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
/*    
    initial set:
    -> at least on eo feach type
    int currant -> where youre at now (vector)
    bitset of taken; take till typestaken=types; push into vector of vectors 
    each new one taken:check if currtaken for that one is whats at the bottom
    boittom:check bottom for tha tione where ur at now for each ttype
    -> replace else no

    -> at each stage after all maximums ->take currmxa - currmin
*/
    int n,k,q;
    cin>>n>>k>>q;
    
    //scout<<"banana";
    queue<pii>nottake; //location, type
    queue<pii>taken;
    vector<vector<int>>bytypes(k+1);
    vector<int>currat(k+1,0);
    int currnum = 0;
    vector<pii>t5;
    //cout<<"start\n";

    for (int a= 1; a <= n; a++)
    {
        cin >>t1>>t2>>t3>>t4;
        t5.pb({t1,t2});
        currnum = currnum | (1<<(t2-1));
    }
    sort(t5.begin(),t5.end());

    for(int a=0;a<n;a++)
    {
        nottake.push(t5[a]);
        bytypes[t5[a].ss].push_back(t5[a].ff);
    }
    //cout<<"currnum: " << currnum<<"\n";
    int constk = k;
    int currmin=nottake.front().ff,currmax = INT_MIN;

    //cout << "curnrum :  " << currnum << "\n";
    for (int a=0;a<k;a++)
    {
        //cout << a << " : " << (currnum & (1<<a) )<< "\n";
        if((currnum & (1<<a)) == 0)
        {
            //cout << "yupe\n";
            for(int a = 1; a <=q;a++)
            {
                cout<<-1 << "\n";
            }
            return 0;
        }
    }

    //cout<<"yey";
    currnum=0; //types taken so far
    while(currnum<k)
    {
        //cout<<"once\n";
        t4 = nottake.front().ss;
        t3 = nottake.front().ff;      
        if(currat[t4]  == 0)
        {
            currnum++;
        }
        currat[t4]++;
        taken.push(nottake.front());
        nottake.pop();
        currmax = taken.back().ff;

        //cout << currat[taken.front().ss] - 1 << "\n";
        while((!taken.empty()) && (bytypes[taken.front().ss][currat[taken.front().ss] - 1] != taken.front().ff))
        {
            //cout << "popped it out\n";
            taken.pop();
            currmin = taken.front().ff;
        }
        //cout << "reached end\n";
    }


    //cout << "init " << currmin << " "  << currmax << "\n";
    vector<int>answers(q+1);
    //cout<<"past init\n";
    vector<pii>queries;
    for(int a=0;a<q;a++)
    {
        cin>>t1>>t2;
        queries.pb({t1,a});
    }
    sort(queries.begin(),queries.end());
    //cout<<"radoifw";

    for(int a= 0;a<q;a++)
    {
        int currque = queries[a].ff;
        //cout<<"querying for " << currque<<'\n';

        //for including currque
        while((!nottake.empty())&&(nottake.front().ff <= currque))
        {
            taken.push(nottake.front());
            nottake.pop();
            currmax = taken.back().ff;
            currat[taken.back().ss]++;
        }
        //cout << "ok bruh " << currmin << " " << currmax << "\n";
        /*cout<<"after includeing currque:\n";
        for(int a=1;a<=k;a++)cout<<currat[a]<<" ";
        cout<<'\n';*/

        int currtype = taken.front().ss;int currpos=taken.front().ff;
        while(bytypes[currtype][currat[currtype] - 1] != currpos)
        {
            //cout << "once " << bytypes[currtype][currat[currtype] - 1] << " " << currpos << "\n";
            taken.pop();
            currmin = taken.front().ff;
            currpos=taken.front().ff;
            currtype = taken.front().ss;
        }
        
        /*cout<<"after popping redundant:\n";
        for(int a=1;a<=k;a++)cout<<currat[a]<<" ";
        cout<<'\n';*/

        while((currat[currtype] < bytypes[currtype].size()) && (abs(currque-bytypes[currtype][currat[currtype]]) < abs(currque-bytypes[currtype][currat[currtype]-1])))
        {
            //cout << "washawasha";
            taken.pop();
            currmin=taken.front().ff;
            taken.push({bytypes[currtype][currat[currtype]],currtype});
            currmax = taken.back().ff;
            currat[taken.back().ss]++;
        }
        //cout<<currmin << " " << currmax <<"\n";
        answers[queries[a].ss] = max(abs(currmax-currque), abs(currmin-currque));
     
        //vector<int>t6(taken.begin(),taken.end())
    }

    //cout << "outputting answers:\n";
    for (int a = 0; a < q;a++)
    {
        cout << answers[a] << "\n";
    }
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:140:33: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         while((currat[currtype] < bytypes[currtype].size()) && (abs(currque-bytypes[currtype][currat[currtype]]) < abs(currque-bytypes[currtype][currat[currtype]-1])))
new_home.cpp:51:9: warning: unused variable 'constk' [-Wunused-variable]
   51 |     int constk = k;
      |         ^~~~~~

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