oj.uz

Submission #815585

# Submission time Handle Problem Language Result Execution time Memory
815585 2023-08-08T17:09:22 Z Ozy New Home (APIO18_new_home) C++17
0 / 100
 286 ms 58272 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_k 400
#define MAX 60000
#define INF (1ll<<60)
//para el vector de orden
#define year first
#define tipo second.first 
#define pos second.second 

lli n,q,k,a,b,c,d;
vector<pair<lli,pll>> orden;
multiset<lli> activos[MAX_k+2];
lli res[MAX];

//solucion de s1 y s2
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({c,{b,a}});
        orden.push_back({d+1,{-b,a}});
    }    
    rep(i,1,q) { //posicion y year
        cin >> a >> b;
        orden.push_back({b,{k+i,a}});
    }
    sort(orden.begin(), orden.end());

    for (auto act : orden) {

        if (act.tipo > k) {
            
            bool sepuede = true;

            act.tipo -= k;
            rep(i,1,k) {
                
                if (activos[i].empty()) {
                    sepuede = false;
                    break;
                }

                auto it  = activos[i].lower_bound(act.pos);
                a = INF;
                b = INF;

                if (it != activos[i].end()) a = (*it) - act.pos;
                if (it != activos[i].begin()) {
                    it--;
                    b = act.pos - (*it);
                }
                res[act.tipo] += min(a,b);
            }

            if (!sepuede) res[act.tipo] = -1;
        }
        else if (act.tipo < 0) {
            act.tipo *= (-1);
            activos[act.tipo].erase( activos[act.tipo].lower_bound(act.pos) );
        }
        else activos[act.tipo].insert(act.pos);

    }

    rep(i,1,q) cout << res[i] << "\n";
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 286 ms 57196 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 257 ms 58272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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