oj.uz

Submission #815773

# Submission time Handle Problem Language Result Execution time Memory
815773 2023-08-08T22:35:14 Z Ozy New Home (APIO18_new_home) C++17
0 / 100
 402 ms 26148 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;
lli res[MAX],vis[MAX+2];

void solve() {
    //inicializa
    lli last[MAX+2];
    set<pll> activos;
    rep(i,1,n) last[i] = INF;

    for (auto act : orden) {
        
        if(act.tipo == 0) {
            if (last[act.id] != INF) activos.erase({last[act.id],act.id});
            last[act.id] = act.pos;
            activos.insert({last[act.id],act.id});
        }
        else {
            if (activos.empty()) continue;
            lli op = (*activos.begin()).first;
            lli mejor = abs( abs(op) - abs(act.pos) ); 
            res[act.id] = max(res[act.id],mejor);
        }

    }
}

//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;
        orden.push_back({a,{0,b}});
        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;
    }

    sort(orden.begin(),orden.end());
    solve();
    for(auto &act : orden) act.pos *= (-1);
    sort(orden.begin(),orden.end());
    solve();

    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 1 ms 2644 KB Output is correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 402 ms 26148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 25016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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