oj.uz

Submission #59891

# Submission time Handle Problem Language Result Execution time Memory
59891 2018-07-23T08:48:39 Z dukati8 New Home (APIO18_new_home) C++14
5 / 100
 5000 ms 93904 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a; i<int(b); i++)
#define all(x) x.begin(),x.end()
int main() {
  int n,q,k;
  cin >> n >> k >> q;
  vector<vector<int> > stores(n);
  rep (i,0,n) {
    int x,t,a,b;
    cin >> x >> t >> a >> b;
    stores[i]={a,b,x,t};
  }
  vector< vector<int> > queries(q);
  rep (i,0,q) {
    int l,y;
    cin >> l >> y;
    queries[i]={y,l,i};
  }
  sort(queries.begin(),queries.end());
  vector<int> answers(q);
  sort(all(stores));
  vector< set<vector<int> > > types(k);
  int numtaken=0;
  set<vector<int> > takenstores;
  rep (i,0,q) {
    int l,y,index;
    l=queries[i][1];
    y=queries[i][0];
    index=queries[i][2];
    while(numtaken<n && y>=stores[numtaken][0]) {
      int x,t,a,b;
      x=stores[numtaken][2];
      t=stores[numtaken][3];
      a=stores[numtaken][0];
      b=stores[numtaken][1];
      takenstores.insert({b,a,x,t});
      types[t-1].insert({x,a,b,t});
      numtaken++;
    }
    while (!takenstores.empty() && (*takenstores.begin())[0]<y) {
      auto it = takenstores.begin();
      int x,t,a,b;
      x=(*it)[2];
      t=(*it)[3];
      a=(*it)[1];
      b=(*it)[0];
      takenstores.erase(it);
      types[t-1].erase({x,a,b,t});
    }
    int best=0;
    rep (ind,0,k) {
      int temp=1e9;
      if (types[ind].empty()) {best=-1; break;}
      auto it = types[ind].upper_bound({l,0,0,0});
      if (it!=types[ind].end()) {
        temp=(*it)[0]-l;
      }
      if (it!=types[ind].begin()) {
        it ==--it;
        temp=min(temp,l-(*it)[0]);
      }
      best=max(best,temp);
    }
    answers[index]=best;
  }
  rep(i,0,q) {
    cout << answers[i] << endl;
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 764 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 5 ms 764 KB Output is correct
14 Correct 7 ms 764 KB Output is correct
15 Correct 14 ms 764 KB Output is correct
16 Correct 10 ms 764 KB Output is correct
17 Correct 6 ms 764 KB Output is correct
18 Correct 9 ms 764 KB Output is correct
19 Correct 9 ms 764 KB Output is correct
20 Correct 6 ms 764 KB Output is correct
21 Correct 11 ms 764 KB Output is correct
22 Correct 8 ms 764 KB Output is correct
23 Correct 10 ms 764 KB Output is correct
24 Correct 9 ms 764 KB Output is correct
25 Correct 5 ms 764 KB Output is correct
26 Correct 6 ms 764 KB Output is correct
27 Correct 5 ms 764 KB Output is correct
28 Correct 6 ms 764 KB Output is correct
29 Correct 4 ms 764 KB Output is correct
30 Correct 5 ms 764 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 764 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 5 ms 764 KB Output is correct
14 Correct 7 ms 764 KB Output is correct
15 Correct 14 ms 764 KB Output is correct
16 Correct 10 ms 764 KB Output is correct
17 Correct 6 ms 764 KB Output is correct
18 Correct 9 ms 764 KB Output is correct
19 Correct 9 ms 764 KB Output is correct
20 Correct 6 ms 764 KB Output is correct
21 Correct 11 ms 764 KB Output is correct
22 Correct 8 ms 764 KB Output is correct
23 Correct 10 ms 764 KB Output is correct
24 Correct 9 ms 764 KB Output is correct
25 Correct 5 ms 764 KB Output is correct
26 Correct 6 ms 764 KB Output is correct
27 Correct 5 ms 764 KB Output is correct
28 Correct 6 ms 764 KB Output is correct
29 Correct 4 ms 764 KB Output is correct
30 Correct 5 ms 764 KB Output is correct
31 Execution timed out 5010 ms 15460 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 5040 ms 93904 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 5100 ms 93904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 764 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 5 ms 764 KB Output is correct
14 Correct 7 ms 764 KB Output is correct
15 Correct 14 ms 764 KB Output is correct
16 Correct 10 ms 764 KB Output is correct
17 Correct 6 ms 764 KB Output is correct
18 Correct 9 ms 764 KB Output is correct
19 Correct 9 ms 764 KB Output is correct
20 Correct 6 ms 764 KB Output is correct
21 Correct 11 ms 764 KB Output is correct
22 Correct 8 ms 764 KB Output is correct
23 Correct 10 ms 764 KB Output is correct
24 Correct 9 ms 764 KB Output is correct
25 Correct 5 ms 764 KB Output is correct
26 Correct 6 ms 764 KB Output is correct
27 Correct 5 ms 764 KB Output is correct
28 Correct 6 ms 764 KB Output is correct
29 Correct 4 ms 764 KB Output is correct
30 Correct 5 ms 764 KB Output is correct
31 Execution timed out 5010 ms 15460 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 600 KB Output is correct
8 Correct 5 ms 724 KB Output is correct
9 Correct 5 ms 764 KB Output is correct
10 Correct 5 ms 764 KB Output is correct
11 Correct 5 ms 764 KB Output is correct
12 Correct 5 ms 764 KB Output is correct
13 Correct 5 ms 764 KB Output is correct
14 Correct 7 ms 764 KB Output is correct
15 Correct 14 ms 764 KB Output is correct
16 Correct 10 ms 764 KB Output is correct
17 Correct 6 ms 764 KB Output is correct
18 Correct 9 ms 764 KB Output is correct
19 Correct 9 ms 764 KB Output is correct
20 Correct 6 ms 764 KB Output is correct
21 Correct 11 ms 764 KB Output is correct
22 Correct 8 ms 764 KB Output is correct
23 Correct 10 ms 764 KB Output is correct
24 Correct 9 ms 764 KB Output is correct
25 Correct 5 ms 764 KB Output is correct
26 Correct 6 ms 764 KB Output is correct
27 Correct 5 ms 764 KB Output is correct
28 Correct 6 ms 764 KB Output is correct
29 Correct 4 ms 764 KB Output is correct
30 Correct 5 ms 764 KB Output is correct
31 Execution timed out 5010 ms 15460 KB Time limit exceeded
32 Halted 0 ms 0 KB -