oj.uz

Submission #106799

# Submission time Handle Problem Language Result Execution time Memory
106799 2019-04-20T14:21:40 Z tictaccat New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 45048 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 3e5 + 10;
const int INF = 1e9;

int n,k,q;

vector<set<pair<int,int>>> types(MAX);
vector<tuple<int,int,int,int,int>> events;
vector<tuple<int,int,int>> queries;
vector<int> answers(MAX);

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n >> k >> q;

    for (int i = 0; i < n; i++) {
        int x,t,a,b; cin >> x >> t >> a >> b;
        events.emplace_back(a,i,x,t,1);
        events.emplace_back(b+1,i,x,t,-1);
    }   

    for (int query = 0; query < q; query++) {
        int l,y; cin >> l >> y; 
        queries.push_back(make_tuple(y,l,query));
    }

    sort(events.begin(),events.end());
    sort(queries.begin(),queries.end());
    int p = 0;

    for (int z = 0; z < q; z++) {
       // cout << "z: " << z << "\n";
        int y,l,query; tie(y,l,query) = queries[z];
        while (p < events.size() && get<0>(events[p]) <= y) {
            int time,i,x,type,change; tie(time,i,x,type,change) = events[p];
            if (change == 1) {
                types[type].insert(make_pair(x,i));
                //cout << "adding: " << type << " " << x << " " << i << "\n";
            }
            if (change == -1) {
                //cout << "removing: " << type << " " << x << " " << i << "\n";
                types[type].erase(make_pair(x,i));
            }
            p++;
        }
        int far = 0;
        for (int type = 1; type <= k; type++) {
            if (types[type].size() == 0) {
               // cout << type << "\n";
                far = -1;
                break;
            }
            auto itRight = types[type].lower_bound(make_pair(y,-1));
            int dist = INF;
            if (itRight != types[type].end()) {
                dist = min(dist,(*itRight).first - l);
            }
            if (itRight != types[type].begin()) {
                auto itLeft = prev(itRight);
                dist = min(dist,(*itLeft).first - l);
            }
            far = max(far,dist);
        }
        answers[query] = far;
    }

    for (int query = 0; query < q; query++) cout << answers[query] << "\n";

    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (p < events.size() && get<0>(events[p]) <= y) {
                ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 44944 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5085 ms 45048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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