oj.uz

Submission #89989

# Submission time Handle Problem Language Result Execution time Memory
89989 2018-12-19T13:30:14 Z tjdgus4384 New Home (APIO18_new_home) C++14
0 / 100
 5000 ms 564988 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
multimap<pair<int, int>, int> m;
multiset<int> typeyear[300001];
multiset<int> yearnum;
vector<pair<int, int> > v[300001];

int main(){
    int n, q, k, x, t, a, b, l, y;
    scanf("%d %d %d", &n, &k, &q);
    for(int i = 0;i < n;i++){
        scanf("%d %d %d %d", &x, &t, &a, &b);
        for(int j = a;j <= b;j++){
            if(typeyear[t].count(j) == 0){
                yearnum.insert(j);
                typeyear[t].insert(j);
            }
            m.insert({{j, t}, x});
            v[t].push_back({j, x});
        }
    }
    for(int i = 0;i <= k;i++) sort(v[i].begin(), v[i].end());
    for(int i = 0;i < q;i++){
        scanf("%d %d", &l, &y);
        if(yearnum.count(y) < k) printf("-1\n");
        else{
            int ans = 0;
            for(int j = 1;j <= k;j++){
                int iter = (int)(lower_bound(v[j].begin(), v[j].end(), make_pair(y, l)) - v[j].begin());
                if(v[j][iter].first != y) iter--;
                int k = abs(v[j][iter].second - l);
                iter--;
                if(v[j][iter].first == y){
                    k = min(k, abs(v[j][iter].second - l));
                }
                ans = max(ans, k);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:29:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(yearnum.count(y) < k) printf("-1\n");
            ~~~~~~~~~~~~~~~~~^~~
new_home.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &k, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &x, &t, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &y);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21496 KB Output is correct
2 Correct 26 ms 21600 KB Output is correct
3 Correct 22 ms 21600 KB Output is correct
4 Execution timed out 5141 ms 564412 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21496 KB Output is correct
2 Correct 26 ms 21600 KB Output is correct
3 Correct 22 ms 21600 KB Output is correct
4 Execution timed out 5141 ms 564412 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5130 ms 564988 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 5074 ms 564988 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21496 KB Output is correct
2 Correct 26 ms 21600 KB Output is correct
3 Correct 22 ms 21600 KB Output is correct
4 Execution timed out 5141 ms 564412 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21496 KB Output is correct
2 Correct 26 ms 21600 KB Output is correct
3 Correct 22 ms 21600 KB Output is correct
4 Execution timed out 5141 ms 564412 KB Time limit exceeded
5 Halted 0 ms 0 KB -