oj.uz

Submission #698639

# Submission time Handle Problem Language Result Execution time Memory
698639 2023-02-14T06:31:54 Z vjudge1 New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 70672 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<pair<int,int> > st;
    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.insert({lc,tp});
        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++) dis[j]=-1;
        auto j=st.begin();
         for (auto &j:st) {
          if (dis[j.second-1]==-1) dis[j.second-1]=abs(j.first-lc);
          else dis[j.second-1]=min(dis[j.second-1],abs(j.first-lc));
        }

        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.erase({lc,tp});
      }
    }

    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++) {
      |                  ~^~~~~~~~~
new_home.cpp:45:14: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   45 |         auto j=st.begin();
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 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 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 3 ms 388 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 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 1 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 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 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 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 3 ms 388 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Execution timed out 5042 ms 13052 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 5083 ms 70672 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 5080 ms 70128 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 1 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 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 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 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 3 ms 388 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Execution timed out 5042 ms 13052 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 1 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 392 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 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 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 328 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 3 ms 388 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 456 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 324 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 332 KB Output is correct
31 Execution timed out 5042 ms 13052 KB Time limit exceeded
32 Halted 0 ms 0 KB -