oj.uz

Submission #815782

# Submission time Handle Problem Language Result Execution time Memory
815782 2023-08-08T23:10:32 Z Ozy New Home (APIO18_new_home) C++17
0 / 100
 420 ms 69100 KB 
#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.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 Runtime error 420 ms 69100 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 58148 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 #6
0 / 20.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 -