oj.uz

Submission #698853

# Submission time Handle Problem Language Result Execution time Memory
698853 2023-02-14T13:33:59 Z vjudge1 New Home (APIO18_new_home) C++17
0 / 100
 5000 ms 48172 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;

    multiset<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++) dis[j]=-1;
         for (int j=0;j<k;j++) {
           auto nm=st[j].lower_bound(lc);
           int lf=-1,rg=-1;
           if (*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);
           }
         }

        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5070 ms 48172 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 5087 ms 45220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -