oj.uz

Submission #5346

# Submission time Handle Problem Language Result Execution time Memory
5346 2014-04-05T17:57:08 Z model_code 버스 (JOI14_bus) C++
100 / 100
 308 ms 10796 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct bus{
  int a,b,x,y;
};

bool operator<(bus b1,bus b2)
{
  return b1.x<b2.x;
}

int main()
{
  int n,m,t=0;
  scanf("%d%d",&n,&m);
  static bus B[300000];
  for(int i=0;i<m;i++){
    scanf("%d%d%d%d",&(B[i].a),&(B[i].b),&(B[i].x),&(B[i].y));
    B[i].a--;
    B[i].b--;
  }
  sort(B,B+m);
  static int E[100000],F[300000];
  for(int i=0;i<n;i++){
    E[i]=-1;
  }
  priority_queue<pair<int,int> > PQ;
  vector<pair<int,int> > K;
  for(int i=0;i<m;i++){
    while(!PQ.empty()&&-PQ.top().first<=B[i].x){
      pair<int,int> pr=PQ.top();
      E[B[pr.second].b]=max(E[B[pr.second].b],F[pr.second]);
      PQ.pop();
    }
    int p;
    if(B[i].a==0){
      p=B[i].x;
    }
    else{
      p=E[B[i].a];
    }
    F[i]=p;
    PQ.push(make_pair(-(B[i].y+t),i));
    if(B[i].b==n-1){
      K.push_back(make_pair(B[i].y,p));
    }
  }
  sort(K.begin(),K.end());
  vector<int> T1,T2;
  int S=-1;
  for(int i=0;i<K.size();i++){
    if(S<K[i].second){
      T1.push_back(K[i].first);
      T2.push_back(K[i].second);
      S=K[i].second;
    }
  }
  int Q;
  scanf("%d",&Q);
  while(Q--){
    int l;
    scanf("%d",&l);
    int i=upper_bound(T1.begin(),T1.end(),l)-T1.begin();
    printf("%d\n",i==0?-1:T2[i-1]);
  }
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7464 KB Output is correct
2 Correct 0 ms 7464 KB Output is correct
3 Correct 0 ms 7464 KB Output is correct
4 Correct 0 ms 7464 KB Output is correct
5 Correct 0 ms 7464 KB Output is correct
6 Correct 0 ms 7464 KB Output is correct
7 Correct 0 ms 7464 KB Output is correct
8 Correct 0 ms 7464 KB Output is correct
9 Correct 0 ms 7464 KB Output is correct
10 Correct 0 ms 7464 KB Output is correct
11 Correct 0 ms 7464 KB Output is correct
12 Correct 0 ms 7464 KB Output is correct
13 Correct 0 ms 7464 KB Output is correct
14 Correct 0 ms 7464 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7464 KB Output is correct
2 Correct 32 ms 7464 KB Output is correct
3 Correct 36 ms 7464 KB Output is correct
4 Correct 4 ms 7464 KB Output is correct
5 Correct 4 ms 7464 KB Output is correct
6 Correct 0 ms 7464 KB Output is correct
7 Correct 24 ms 7464 KB Output is correct
8 Correct 0 ms 7464 KB Output is correct
9 Correct 28 ms 7464 KB Output is correct
10 Correct 36 ms 7464 KB Output is correct
11 Correct 24 ms 7464 KB Output is correct
12 Correct 36 ms 7464 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 10540 KB Output is correct
2 Correct 264 ms 10540 KB Output is correct
3 Correct 260 ms 10540 KB Output is correct
4 Correct 272 ms 10540 KB Output is correct
5 Correct 264 ms 10540 KB Output is correct
6 Correct 264 ms 10540 KB Output is correct
7 Correct 248 ms 10540 KB Output is correct
8 Correct 260 ms 10796 KB Output is correct
9 Correct 252 ms 10540 KB Output is correct
10 Correct 244 ms 10540 KB Output is correct
11 Correct 244 ms 10540 KB Output is correct
12 Correct 252 ms 10540 KB Output is correct
13 Correct 252 ms 10540 KB Output is correct
14 Correct 252 ms 10540 KB Output is correct
15 Correct 232 ms 10540 KB Output is correct
16 Correct 56 ms 7464 KB Output is correct
17 Correct 64 ms 7464 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 10540 KB Output is correct
2 Correct 272 ms 10540 KB Output is correct
3 Correct 308 ms 10540 KB Output is correct
4 Correct 304 ms 10540 KB Output is correct
5 Correct 292 ms 10540 KB Output is correct
6 Correct 300 ms 10540 KB Output is correct
7 Correct 284 ms 10540 KB Output is correct
8 Correct 300 ms 10540 KB Output is correct
9 Correct 288 ms 10540 KB Output is correct
10 Correct 276 ms 10540 KB Output is correct
11 Correct 268 ms 10540 KB Output is correct
12 Correct 296 ms 10540 KB Output is correct
13 Correct 272 ms 10540 KB Output is correct
14 Correct 276 ms 10540 KB Output is correct
15 Correct 288 ms 10540 KB Output is correct
16 Correct 84 ms 7464 KB Output is correct