Submission #815782

#	Time	Username	Problem	Language	Result	Execution time	Memory
815782		Ozy	New Home (APIO18_new_home)	C++17	0 / 100	420 ms	69100 KiB

new_home

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a <<  " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli> 

#define MAX 300000
#define INF (1ll<<60)
#define LIM 10000000000
//para el vector de orden
#define pos first
#define tipo second.first 
#define id second.second 

lli n,q,k,a,b,c,d,dif;
vector<pair<lli,pll>> orden;
vector<lli> tipo_t[MAX+2];
lli res[MAX],vis[MAX+2];
set<pll> activos;
lli apu[MAX+2];

//solucion de s3
int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k >> q;
    rep(i,1,n) {
        cin >> a >> b >> c >> d;
        tipo_t[b].push_back(a);

        if (!vis[b]) {
            vis[b] = 1;
            dif++;
        }
    }    
    rep(i,1,q) {
        cin >> a >> b;
        orden.push_back({a,{1,i}});
    }

    if(dif < k) {
        rep(i,1,q) cout << "-1\n";
        return 0;
    }//correcto

    rep(i,1,k) {
        a = 0;
        sort(tipo_t[i].begin(), tipo_t[i].end());
        for (auto act : tipo_t[i]) {
            if (a == 0) b = 0;
            else b = (act+a+1)/2;
            orden.push_back({b,{0,i}});
            a = act;
        }        
    }

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

    for(auto act : orden) {
        if (act.tipo == 0) {
            if(apu[act.id] > 0) activos.erase({tipo_t[act.id][apu[act.id]-1],act.id});
            activos.insert({tipo_t[act.id][apu[act.id]],act.id});
            apu[act.id]++;
        }
        else {
            a = (*activos.begin()).first;
            b = (*activos.rbegin()).first;
            a = abs(a - act.pos);
            b = abs(b - act.pos);
            res[act.id] = max(a,b);
        }
    }

    rep(i,1,q) if (res[i] > LIM) cout << "-1\n"; 
    else cout << res[i] << "\n";
    return 0;
}

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