답안 #59891 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59891	2018-07-23T08:48:39 Z	dukati8	새 집 (APIO18_new_home)	C++14	5 / 100	5000 ms	93904 KB

new_home

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5040 ms	93904 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5100 ms	93904 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #59891

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0