Submission #815789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
815789	2023-08-08T23:18:22 Z	Ozy	New Home (APIO18_new_home)	C++17	0 / 100	652 ms	73268 KB

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
//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+2],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,n) cout << res[i] << "\n";
    return 0;
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7380 KB	Output is correct
2	Incorrect	3 ms	7380 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7380 KB	Output is correct
2	Incorrect	3 ms	7380 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	398 ms	37120 KB	Output is correct
2	Correct	245 ms	47128 KB	Output is correct
3	Correct	573 ms	73268 KB	Output is correct
4	Correct	652 ms	52824 KB	Output is correct
5	Correct	301 ms	49900 KB	Output is correct
6	Correct	237 ms	47240 KB	Output is correct
7	Correct	328 ms	73216 KB	Output is correct
8	Correct	436 ms	52160 KB	Output is correct
9	Correct	391 ms	49468 KB	Output is correct
10	Correct	276 ms	48376 KB	Output is correct
11	Incorrect	254 ms	47352 KB	Output isn't correct
12	Halted	0 ms	0 KB	-