oj.uz

Submission #698922

# Submission time Handle Problem Language Result Execution time Memory
698922 2023-02-14T19:52:02 Z vjudge1 New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 74640 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl "\n"
int mod=1e9+7;
const int N=1e5+5;
template<class x>
using ordered_multiset = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    int n,k,q; cin>>n>>k>>q;
    vector<pair<int,pair<int,pair<int,int> > > > v;
    for (int i=0;i<n;i++) {
      int a,b,c,d; cin>>a>>b>>c>>d;
      v.push_back({c,{0,{a,b}}});
      v.push_back({d,{2,{a,b}}});
    }
    for (int i=0;i<q;i++) {
      int l,y; cin>>l>>y;
      v.push_back({y,{1,{l,i}}});
    }
    sort(v.begin(),v.end());

    int ans[q];
    int dis[k];
    for (int i=0;i<q;i++) ans[i]=-1;

    set<int> st[k];
    map<pair<int,int>,int> mp;
    for (int i=0;i<v.size();i++) {
      if (v[i].second.first==0) {
        int lc=v[i].second.second.first,tp=v[i].second.second.second;
        if (mp[{lc,tp}]==0) st[tp-1].insert(lc);
        mp[{lc,tp}]++;
      }
      else if (v[i].second.first==1) {
        int lc=v[i].second.second.first,indx=v[i].second.second.second;
         for (int j=0;j<k;j++) {
           auto nm=st[j].lower_bound(lc);
           int lf=-1,rg=-1;
           if (mp[{*nm,j+1}]>0 && *nm>=lc) rg=abs(*nm-lc);
           if (nm!=st[j].begin()) {nm--; lf=abs(lc-*nm);}
           if (lf==-1) {
             if (rg==-1) dis[j]=-1;
             else dis[j]=rg;
           }
           else {
             if (rg==-1) dis[j]=lf;
             else dis[j]=min(lf,rg);
           }
           if (dis[j]==-1) break;
         }

        int mx=0;
        for (int j=0;j<k;j++) {
          if (dis[j]==-1) {mx=-1; break;}
          mx=max(mx,dis[j]);
        }
        ans[indx]=mx;
      }
      else {
        int lc=v[i].second.second.first,tp=v[i].second.second.second;
        mp[{lc,tp}]--;
        if (mp[{lc,tp}]==0) st[tp-1].erase(lc);
      }
    }

    for (int i=0;i<q;i++) cout<<ans[i]<<endl;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:36:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i=0;i<v.size();i++) {
      |                  ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 6 ms 340 KB Output is correct
22 Correct 4 ms 388 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 352 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 392 KB Output is correct
29 Correct 1 ms 396 KB Output is correct
30 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 6 ms 340 KB Output is correct
22 Correct 4 ms 388 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 352 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 392 KB Output is correct
29 Correct 1 ms 396 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Execution timed out 5031 ms 17752 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5011 ms 74640 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 5020 ms 68720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 6 ms 340 KB Output is correct
22 Correct 4 ms 388 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 352 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 392 KB Output is correct
29 Correct 1 ms 396 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Execution timed out 5031 ms 17752 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 388 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 3 ms 332 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 2 ms 336 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 6 ms 340 KB Output is correct
22 Correct 4 ms 388 KB Output is correct
23 Correct 3 ms 340 KB Output is correct
24 Correct 3 ms 352 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 392 KB Output is correct
29 Correct 1 ms 396 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Execution timed out 5031 ms 17752 KB Time limit exceeded
32 Halted 0 ms 0 KB -