Submission #815793

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
815793	2023-08-08T23:25:24 Z	Ozy	New Home (APIO18_new_home)	C++17	10 / 100	416 ms	59340 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,q) 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
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	400 ms	37036 KB	Output is correct
2	Correct	236 ms	34468 KB	Output is correct
3	Correct	403 ms	59340 KB	Output is correct
4	Correct	416 ms	39140 KB	Output is correct
5	Correct	237 ms	37408 KB	Output is correct
6	Correct	226 ms	34696 KB	Output is correct
7	Correct	389 ms	59316 KB	Output is correct
8	Correct	409 ms	38516 KB	Output is correct
9	Correct	365 ms	35868 KB	Output is correct
10	Correct	276 ms	35416 KB	Output is correct
11	Correct	225 ms	34700 KB	Output is correct
12	Correct	250 ms	48308 KB	Output is correct