oj.uz

Submission #60139

# Submission time Handle Problem Language Result Execution time Memory
60139 2018-07-23T17:44:27 Z duality New Home (APIO18_new_home) C++11
12 / 100
 3606 ms 87552 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long int LLI;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;

struct op { int time,t,x,i; };
bool comp(op a,op b) {
    if (a.time == b.time) return a.t > b.t;
    else return a.time < b.time;
}
vector<op> oper;
multiset<int> stores[400];
int ans[300000];
int main() {
    int i;
    int n,k,q;
    int x,t,a,b,l,y;
    scanf("%d %d %d",&n,&k,&q);
    for (i = 0; i < n; i++) {
        scanf("%d %d %d %d",&x,&t,&a,&b);
        oper.pb((op){a,t,x,-1});
        oper.pb((op){b,-t,x,-1});
    }
    for (i = 0; i < q; i++) {
        scanf("%d %d",&l,&y);
        oper.pb((op){y,0,l,i});
    }
    sort(oper.begin(),oper.end(),comp);

    int j;
    for (i = 0; i < oper.size(); i++) {
        if (oper[i].t > 0) stores[oper[i].t-1].insert(oper[i].x);
        else if (oper[i].t < 0) stores[-oper[i].t-1].erase(stores[-oper[i].t-1].find(oper[i].x));
        else {
            int m = 0;
            for (j = 0; j < k; j++) {
                if (stores[j].empty()) break;
                else {
                    auto it = stores[j].lower_bound(oper[i].x);
                    int mm = 1e9;
                    if (it != stores[j].end()) mm = min(mm,*it-oper[i].x);
                    if (it != stores[j].begin()) mm = min(mm,oper[i].x-*(--it));
                    m = max(m,mm);
                }
            }
            if (j < k) ans[oper[i].i] = -1;
            else ans[oper[i].i] = m;
        }
    }
    for (i = 0; i < q; i++) printf("%d\n",ans[i]);

    return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < oper.size(); i++) {
                 ~~^~~~~~~~~~~~~
new_home.cpp:22: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:24: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:29: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 4 ms 644 KB Output is correct
9 Correct 4 ms 696 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 4 ms 744 KB Output is correct
13 Correct 5 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 4 ms 796 KB Output is correct
16 Correct 4 ms 796 KB Output is correct
17 Correct 4 ms 796 KB Output is correct
18 Correct 4 ms 796 KB Output is correct
19 Correct 3 ms 796 KB Output is correct
20 Correct 3 ms 796 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 4 ms 796 KB Output is correct
23 Correct 5 ms 796 KB Output is correct
24 Correct 3 ms 796 KB Output is correct
25 Correct 3 ms 796 KB Output is correct
26 Correct 4 ms 796 KB Output is correct
27 Correct 3 ms 796 KB Output is correct
28 Correct 3 ms 796 KB Output is correct
29 Correct 4 ms 796 KB Output is correct
30 Correct 4 ms 872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 4 ms 644 KB Output is correct
9 Correct 4 ms 696 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 4 ms 744 KB Output is correct
13 Correct 5 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 4 ms 796 KB Output is correct
16 Correct 4 ms 796 KB Output is correct
17 Correct 4 ms 796 KB Output is correct
18 Correct 4 ms 796 KB Output is correct
19 Correct 3 ms 796 KB Output is correct
20 Correct 3 ms 796 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 4 ms 796 KB Output is correct
23 Correct 5 ms 796 KB Output is correct
24 Correct 3 ms 796 KB Output is correct
25 Correct 3 ms 796 KB Output is correct
26 Correct 4 ms 796 KB Output is correct
27 Correct 3 ms 796 KB Output is correct
28 Correct 3 ms 796 KB Output is correct
29 Correct 4 ms 796 KB Output is correct
30 Correct 4 ms 872 KB Output is correct
31 Correct 3606 ms 7684 KB Output is correct
32 Correct 149 ms 7684 KB Output is correct
33 Correct 315 ms 9964 KB Output is correct
34 Correct 2635 ms 12868 KB Output is correct
35 Correct 1840 ms 17696 KB Output is correct
36 Correct 371 ms 20364 KB Output is correct
37 Correct 230 ms 20748 KB Output is correct
38 Correct 149 ms 23556 KB Output is correct
39 Correct 143 ms 26328 KB Output is correct
40 Correct 140 ms 29156 KB Output is correct
41 Correct 344 ms 32344 KB Output is correct
42 Correct 332 ms 35068 KB Output is correct
43 Correct 914 ms 40356 KB Output is correct
44 Correct 272 ms 40412 KB Output is correct
45 Correct 167 ms 43304 KB Output is correct
46 Correct 157 ms 46192 KB Output is correct
47 Correct 99 ms 48928 KB Output is correct
48 Correct 108 ms 51696 KB Output is correct
49 Correct 138 ms 54396 KB Output is correct
50 Correct 271 ms 57256 KB Output is correct
51 Correct 146 ms 60180 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 481 ms 85204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 469 ms 87552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 4 ms 644 KB Output is correct
9 Correct 4 ms 696 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 4 ms 744 KB Output is correct
13 Correct 5 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 4 ms 796 KB Output is correct
16 Correct 4 ms 796 KB Output is correct
17 Correct 4 ms 796 KB Output is correct
18 Correct 4 ms 796 KB Output is correct
19 Correct 3 ms 796 KB Output is correct
20 Correct 3 ms 796 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 4 ms 796 KB Output is correct
23 Correct 5 ms 796 KB Output is correct
24 Correct 3 ms 796 KB Output is correct
25 Correct 3 ms 796 KB Output is correct
26 Correct 4 ms 796 KB Output is correct
27 Correct 3 ms 796 KB Output is correct
28 Correct 3 ms 796 KB Output is correct
29 Correct 4 ms 796 KB Output is correct
30 Correct 4 ms 872 KB Output is correct
31 Correct 3606 ms 7684 KB Output is correct
32 Correct 149 ms 7684 KB Output is correct
33 Correct 315 ms 9964 KB Output is correct
34 Correct 2635 ms 12868 KB Output is correct
35 Correct 1840 ms 17696 KB Output is correct
36 Correct 371 ms 20364 KB Output is correct
37 Correct 230 ms 20748 KB Output is correct
38 Correct 149 ms 23556 KB Output is correct
39 Correct 143 ms 26328 KB Output is correct
40 Correct 140 ms 29156 KB Output is correct
41 Correct 344 ms 32344 KB Output is correct
42 Correct 332 ms 35068 KB Output is correct
43 Correct 914 ms 40356 KB Output is correct
44 Correct 272 ms 40412 KB Output is correct
45 Correct 167 ms 43304 KB Output is correct
46 Correct 157 ms 46192 KB Output is correct
47 Correct 99 ms 48928 KB Output is correct
48 Correct 108 ms 51696 KB Output is correct
49 Correct 138 ms 54396 KB Output is correct
50 Correct 271 ms 57256 KB Output is correct
51 Correct 146 ms 60180 KB Output is correct
52 Runtime error 120 ms 87552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 4 ms 544 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 4 ms 624 KB Output is correct
8 Correct 4 ms 644 KB Output is correct
9 Correct 4 ms 696 KB Output is correct
10 Correct 4 ms 736 KB Output is correct
11 Correct 4 ms 736 KB Output is correct
12 Correct 4 ms 744 KB Output is correct
13 Correct 5 ms 744 KB Output is correct
14 Correct 3 ms 744 KB Output is correct
15 Correct 4 ms 796 KB Output is correct
16 Correct 4 ms 796 KB Output is correct
17 Correct 4 ms 796 KB Output is correct
18 Correct 4 ms 796 KB Output is correct
19 Correct 3 ms 796 KB Output is correct
20 Correct 3 ms 796 KB Output is correct
21 Correct 3 ms 796 KB Output is correct
22 Correct 4 ms 796 KB Output is correct
23 Correct 5 ms 796 KB Output is correct
24 Correct 3 ms 796 KB Output is correct
25 Correct 3 ms 796 KB Output is correct
26 Correct 4 ms 796 KB Output is correct
27 Correct 3 ms 796 KB Output is correct
28 Correct 3 ms 796 KB Output is correct
29 Correct 4 ms 796 KB Output is correct
30 Correct 4 ms 872 KB Output is correct
31 Correct 3606 ms 7684 KB Output is correct
32 Correct 149 ms 7684 KB Output is correct
33 Correct 315 ms 9964 KB Output is correct
34 Correct 2635 ms 12868 KB Output is correct
35 Correct 1840 ms 17696 KB Output is correct
36 Correct 371 ms 20364 KB Output is correct
37 Correct 230 ms 20748 KB Output is correct
38 Correct 149 ms 23556 KB Output is correct
39 Correct 143 ms 26328 KB Output is correct
40 Correct 140 ms 29156 KB Output is correct
41 Correct 344 ms 32344 KB Output is correct
42 Correct 332 ms 35068 KB Output is correct
43 Correct 914 ms 40356 KB Output is correct
44 Correct 272 ms 40412 KB Output is correct
45 Correct 167 ms 43304 KB Output is correct
46 Correct 157 ms 46192 KB Output is correct
47 Correct 99 ms 48928 KB Output is correct
48 Correct 108 ms 51696 KB Output is correct
49 Correct 138 ms 54396 KB Output is correct
50 Correct 271 ms 57256 KB Output is correct
51 Correct 146 ms 60180 KB Output is correct
52 Runtime error 481 ms 85204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
53 Halted 0 ms 0 KB -