oj.uz

Submission #744520

# Submission time Handle Problem Language Result Execution time Memory
744520 2023-05-18T16:27:20 Z Abito New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 193128 KB 
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define endl '\n'
#define ep insert
#define pow pwr
#define sqrt sqrtt
#define elif else if
#define y1 YONE
#define int long long
using namespace std;
const int N=1e6+5;
int n,k,q,d[N];
// X , T , L , R
pair<pair<int,int>,pair<int,int>> a[N];
//Y X I
pair<pair<int,int>,int> b[N];
//map for compress
map<int,int> mp;
//v[0] adding , v[1] removing
vector<pair<int,int>> v[2][N];
//for each k what it has
map<int,int> s[N];
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>k>>q;
    for (int i=1;i<=n;i++){
        cin>>a[i].F.F>>a[i].F.S>>a[i].S.F>>a[i].S.S;
        mp[a[i].S.F]++;
        mp[a[i].S.S]++;
    }
    for (int i=1;i<=q;i++){
        cin>>b[i].F.S>>b[i].F.F;
        b[i].S=i;
        mp[b[i].F.F]++;
    }
    int c=0;
    for (auto u:mp){
        c++;
        mp[u.F]=c;
    }
    for (int i=1;i<=n;i++){
        a[i].S.F=mp[a[i].S.F];
        a[i].S.S=mp[a[i].S.S];
        v[0][a[i].S.F].pb(a[i].F);
        v[1][a[i].S.S].pb(a[i].F);
    }
    for (int i=1;i<=q;i++) b[i].F.F=mp[b[i].F.F];
    sort(b+1,b+1+q);
    int j=1;
    for (int i=1;i<=c;i++){
        for (auto u:v[0][i]) s[u.S][u.F]++;
        while (b[j].F.F<i) j++;
        while (b[j].F.F==i){
            int ans=INT_MIN;
            for (int l=1;l<=k;l++){
                int ansx=INT_MAX;
                auto it=s[l].lower_bound(b[j].F.S);
                if (it!=s[l].end()) ansx=min(ansx,abs((*it).F-b[j].F.S));
                if (it!=s[l].begin()) --it;
                if (it!=s[l].end()) ansx=min(ansx,abs((*it).F-b[j].F.S));
                ans=max(ans,ansx);
            }
            if (ans==INT_MAX) ans=-1;
            d[b[j].S]=ans;
            j++;
        }
        for (auto u:v[1][i]){
            s[u.S][u.F]--;
            if (s[u.S][u.F]==0) s[u.S].erase(s[u.S].find(u.F));
        }
    }
    for (int i=1;i<=q;i++) cout<<d[i]<<endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 52 ms 94280 KB Output is correct
3 Correct 42 ms 94260 KB Output is correct
4 Correct 46 ms 94184 KB Output is correct
5 Correct 44 ms 94324 KB Output is correct
6 Correct 47 ms 94440 KB Output is correct
7 Correct 52 ms 94376 KB Output is correct
8 Correct 55 ms 94412 KB Output is correct
9 Correct 48 ms 94384 KB Output is correct
10 Correct 48 ms 94472 KB Output is correct
11 Correct 50 ms 94408 KB Output is correct
12 Correct 52 ms 94376 KB Output is correct
13 Correct 56 ms 94388 KB Output is correct
14 Correct 49 ms 94388 KB Output is correct
15 Correct 47 ms 94376 KB Output is correct
16 Correct 44 ms 94296 KB Output is correct
17 Correct 48 ms 94456 KB Output is correct
18 Correct 49 ms 94424 KB Output is correct
19 Correct 51 ms 94404 KB Output is correct
20 Correct 49 ms 94464 KB Output is correct
21 Correct 51 ms 94252 KB Output is correct
22 Correct 50 ms 94412 KB Output is correct
23 Correct 53 ms 94376 KB Output is correct
24 Correct 49 ms 94380 KB Output is correct
25 Correct 53 ms 94412 KB Output is correct
26 Correct 43 ms 94312 KB Output is correct
27 Correct 45 ms 94264 KB Output is correct
28 Correct 52 ms 94424 KB Output is correct
29 Correct 45 ms 94548 KB Output is correct
30 Correct 52 ms 94428 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 52 ms 94280 KB Output is correct
3 Correct 42 ms 94260 KB Output is correct
4 Correct 46 ms 94184 KB Output is correct
5 Correct 44 ms 94324 KB Output is correct
6 Correct 47 ms 94440 KB Output is correct
7 Correct 52 ms 94376 KB Output is correct
8 Correct 55 ms 94412 KB Output is correct
9 Correct 48 ms 94384 KB Output is correct
10 Correct 48 ms 94472 KB Output is correct
11 Correct 50 ms 94408 KB Output is correct
12 Correct 52 ms 94376 KB Output is correct
13 Correct 56 ms 94388 KB Output is correct
14 Correct 49 ms 94388 KB Output is correct
15 Correct 47 ms 94376 KB Output is correct
16 Correct 44 ms 94296 KB Output is correct
17 Correct 48 ms 94456 KB Output is correct
18 Correct 49 ms 94424 KB Output is correct
19 Correct 51 ms 94404 KB Output is correct
20 Correct 49 ms 94464 KB Output is correct
21 Correct 51 ms 94252 KB Output is correct
22 Correct 50 ms 94412 KB Output is correct
23 Correct 53 ms 94376 KB Output is correct
24 Correct 49 ms 94380 KB Output is correct
25 Correct 53 ms 94412 KB Output is correct
26 Correct 43 ms 94312 KB Output is correct
27 Correct 45 ms 94264 KB Output is correct
28 Correct 52 ms 94424 KB Output is correct
29 Correct 45 ms 94548 KB Output is correct
30 Correct 52 ms 94428 KB Output is correct
31 Correct 2029 ms 120252 KB Output is correct
32 Correct 95 ms 101464 KB Output is correct
33 Correct 398 ms 117656 KB Output is correct
34 Correct 1901 ms 117940 KB Output is correct
35 Correct 1090 ms 120268 KB Output is correct
36 Correct 421 ms 120032 KB Output is correct
37 Correct 319 ms 116556 KB Output is correct
38 Correct 251 ms 116548 KB Output is correct
39 Correct 229 ms 116252 KB Output is correct
40 Correct 214 ms 116360 KB Output is correct
41 Correct 469 ms 116488 KB Output is correct
42 Correct 507 ms 116352 KB Output is correct
43 Correct 161 ms 102900 KB Output is correct
44 Correct 393 ms 116508 KB Output is correct
45 Correct 279 ms 116444 KB Output is correct
46 Correct 225 ms 116392 KB Output is correct
47 Correct 162 ms 115500 KB Output is correct
48 Correct 165 ms 115304 KB Output is correct
49 Correct 187 ms 115788 KB Output is correct
50 Correct 313 ms 116088 KB Output is correct
51 Correct 172 ms 115744 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 168832 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 5039 ms 193128 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 52 ms 94280 KB Output is correct
3 Correct 42 ms 94260 KB Output is correct
4 Correct 46 ms 94184 KB Output is correct
5 Correct 44 ms 94324 KB Output is correct
6 Correct 47 ms 94440 KB Output is correct
7 Correct 52 ms 94376 KB Output is correct
8 Correct 55 ms 94412 KB Output is correct
9 Correct 48 ms 94384 KB Output is correct
10 Correct 48 ms 94472 KB Output is correct
11 Correct 50 ms 94408 KB Output is correct
12 Correct 52 ms 94376 KB Output is correct
13 Correct 56 ms 94388 KB Output is correct
14 Correct 49 ms 94388 KB Output is correct
15 Correct 47 ms 94376 KB Output is correct
16 Correct 44 ms 94296 KB Output is correct
17 Correct 48 ms 94456 KB Output is correct
18 Correct 49 ms 94424 KB Output is correct
19 Correct 51 ms 94404 KB Output is correct
20 Correct 49 ms 94464 KB Output is correct
21 Correct 51 ms 94252 KB Output is correct
22 Correct 50 ms 94412 KB Output is correct
23 Correct 53 ms 94376 KB Output is correct
24 Correct 49 ms 94380 KB Output is correct
25 Correct 53 ms 94412 KB Output is correct
26 Correct 43 ms 94312 KB Output is correct
27 Correct 45 ms 94264 KB Output is correct
28 Correct 52 ms 94424 KB Output is correct
29 Correct 45 ms 94548 KB Output is correct
30 Correct 52 ms 94428 KB Output is correct
31 Correct 2029 ms 120252 KB Output is correct
32 Correct 95 ms 101464 KB Output is correct
33 Correct 398 ms 117656 KB Output is correct
34 Correct 1901 ms 117940 KB Output is correct
35 Correct 1090 ms 120268 KB Output is correct
36 Correct 421 ms 120032 KB Output is correct
37 Correct 319 ms 116556 KB Output is correct
38 Correct 251 ms 116548 KB Output is correct
39 Correct 229 ms 116252 KB Output is correct
40 Correct 214 ms 116360 KB Output is correct
41 Correct 469 ms 116488 KB Output is correct
42 Correct 507 ms 116352 KB Output is correct
43 Correct 161 ms 102900 KB Output is correct
44 Correct 393 ms 116508 KB Output is correct
45 Correct 279 ms 116444 KB Output is correct
46 Correct 225 ms 116392 KB Output is correct
47 Correct 162 ms 115500 KB Output is correct
48 Correct 165 ms 115304 KB Output is correct
49 Correct 187 ms 115788 KB Output is correct
50 Correct 313 ms 116088 KB Output is correct
51 Correct 172 ms 115744 KB Output is correct
52 Execution timed out 5072 ms 117812 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94156 KB Output is correct
2 Correct 52 ms 94280 KB Output is correct
3 Correct 42 ms 94260 KB Output is correct
4 Correct 46 ms 94184 KB Output is correct
5 Correct 44 ms 94324 KB Output is correct
6 Correct 47 ms 94440 KB Output is correct
7 Correct 52 ms 94376 KB Output is correct
8 Correct 55 ms 94412 KB Output is correct
9 Correct 48 ms 94384 KB Output is correct
10 Correct 48 ms 94472 KB Output is correct
11 Correct 50 ms 94408 KB Output is correct
12 Correct 52 ms 94376 KB Output is correct
13 Correct 56 ms 94388 KB Output is correct
14 Correct 49 ms 94388 KB Output is correct
15 Correct 47 ms 94376 KB Output is correct
16 Correct 44 ms 94296 KB Output is correct
17 Correct 48 ms 94456 KB Output is correct
18 Correct 49 ms 94424 KB Output is correct
19 Correct 51 ms 94404 KB Output is correct
20 Correct 49 ms 94464 KB Output is correct
21 Correct 51 ms 94252 KB Output is correct
22 Correct 50 ms 94412 KB Output is correct
23 Correct 53 ms 94376 KB Output is correct
24 Correct 49 ms 94380 KB Output is correct
25 Correct 53 ms 94412 KB Output is correct
26 Correct 43 ms 94312 KB Output is correct
27 Correct 45 ms 94264 KB Output is correct
28 Correct 52 ms 94424 KB Output is correct
29 Correct 45 ms 94548 KB Output is correct
30 Correct 52 ms 94428 KB Output is correct
31 Correct 2029 ms 120252 KB Output is correct
32 Correct 95 ms 101464 KB Output is correct
33 Correct 398 ms 117656 KB Output is correct
34 Correct 1901 ms 117940 KB Output is correct
35 Correct 1090 ms 120268 KB Output is correct
36 Correct 421 ms 120032 KB Output is correct
37 Correct 319 ms 116556 KB Output is correct
38 Correct 251 ms 116548 KB Output is correct
39 Correct 229 ms 116252 KB Output is correct
40 Correct 214 ms 116360 KB Output is correct
41 Correct 469 ms 116488 KB Output is correct
42 Correct 507 ms 116352 KB Output is correct
43 Correct 161 ms 102900 KB Output is correct
44 Correct 393 ms 116508 KB Output is correct
45 Correct 279 ms 116444 KB Output is correct
46 Correct 225 ms 116392 KB Output is correct
47 Correct 162 ms 115500 KB Output is correct
48 Correct 165 ms 115304 KB Output is correct
49 Correct 187 ms 115788 KB Output is correct
50 Correct 313 ms 116088 KB Output is correct
51 Correct 172 ms 115744 KB Output is correct
52 Execution timed out 5102 ms 168832 KB Time limit exceeded
53 Halted 0 ms 0 KB -