結果

問題 No.953 席
ユーザー LayCurseLayCurse
提出日時 2019-12-17 15:43:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,985 bytes
コンパイル時間 3,181 ms
コンパイル使用メモリ 229,116 KB
実行使用メモリ 14,080 KB
最終ジャッジ日時 2024-07-02 21:27:03
合計ジャッジ時間 6,085 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 29 ms
6,144 KB
testcase_03 AC 27 ms
5,760 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 89 ms
10,624 KB
testcase_09 AC 115 ms
14,080 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 50 ms
8,832 KB
testcase_13 AC 71 ms
10,368 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 42 ms
8,192 KB
testcase_17 AC 62 ms
9,216 KB
testcase_18 AC 54 ms
8,576 KB
testcase_19 WA -
testcase_20 AC 54 ms
8,704 KB
testcase_21 AC 35 ms
6,528 KB
testcase_22 AC 51 ms
9,216 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 82 ms
10,624 KB
testcase_26 AC 15 ms
5,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int K1;
int K2;
int Q;
long long A[100000];
long long B[100000];
int ind[100000];
int cnv[100000];
int nx[100000][2];
set<int> ok1;
set<int> ok2;
priority_queue< pair<long long,int> > q;
int res[100000];
int main(){
  int i;
  int j;
  int k;
  int x;
  int y;
  int z;
  long long tm;
  rd(N);
  rd(K1);K1 += (-1);
  rd(K2);K2 += (-1);
  rd(Q);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(Q);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
      rd(B[Lj4PdHRW]);
    }
  }
  k = 0;
  if(K1 < K2){
    while(K1 >= 0 || K2 < N){
      if(K1 >= 0){
        ind[k++] = K1--;
      }
      if(K2 <  N){
        ind[k++] = K2++;
      }
    }
  }
  else{
    while(K1 < 0 || K2 >= N){
      if(K1 <  N){
        ind[k++] = K1++;
      }
      if(K2 >= 0){
        ind[k++] = K2--;
      }
    }
  }
  for(i=(0);i<(N);i++){
    cnv[ind[i]] = i;
  }
  for(i=(0);i<(N);i++){
    nx[cnv[i]][0] = nx[cnv[i]][1] = -1;
    if(i-1 >= 0){
      nx[cnv[i]][0] = cnv[i-1];
    }
    if(i+1 <  N){
      nx[cnv[i]][1] = cnv[i+1];
    }
  }
  for(i=(0);i<(N);i++){
    ok1.insert(i);
  }
  for(i=(0);i<(N);i++){
    ok2.insert(i);
  }
  tm = 0;
  for(k=(0);k<(Q);k++){
    chmax(tm, A[k]);
    while(ok1.size()==0 || (q.size() && -q.top().first <= tm)){
      chmax(tm, -q.top().first);
      i = q.top().second;
      q.pop();
      ok1.insert(i);
      for(z=(0);z<(3);z++){
        x = i;
        if(z < 2){
          x = nx[i][z];
        }
        if(x==-1){
          continue;
        }
        if(ok1.count(x)==0){
          continue;
        }
        if((nx[x][0]==-1 || ok1.count(nx[x][0])==1) && (nx[x][1]==-1 || ok1.count(nx[x][1])==1)){
          ok2.insert(x);
        }
      }
    }
    if(ok2.size()){
      i = *ok2.begin();
    }
    else{
      i = *ok1.begin();
    }
    q.push( make_pair(-(tm + B[k]), i) );
    res[k] = i;
    ok1.erase(i);
    for(z=(0);z<(3);z++){
      x = i;
      if(z < 2){
        x = nx[i][z];
      }
      if(x==-1){
        continue;
      }
      if(ok2.count(x)){
        ok2.erase(x);
      }
    }
  }
  for(i=(0);i<(Q);i++){
    wt_L(ind[res[i]] + 1);
    wt_L('\n');
  }
  return 0;
}
// cLay varsion 20191214-1

// --- original code ---
// int N, K1, K2;
// int Q; ll A[1d5], B[1d5];
// 
// int ind[1d5], cnv[1d5], nx[1d5][2];
// set<int> ok1, ok2;
// 
// priority_queue< pair<ll,int> > q;
// int res[1d5];
// 
// {
//   int i, j, k, x, y, z;
//   ll tm;
//   rd(N,K1--,K2--,Q,(A,B)(Q));
// 
//   k = 0;
//   if(K1 < K2){
//     while(K1 >= 0 || K2 < N){
//       if(K1 >= 0) ind[k++] = K1--;
//       if(K2 <  N) ind[k++] = K2++;
//     }
//   } else {
//     while(K1 < 0 || K2 >= N){
//       if(K1 <  N) ind[k++] = K1++;
//       if(K2 >= 0) ind[k++] = K2--;
//     }
//   }
// 
//   rep(i,N) cnv[ind[i]] = i;
//   rep(i,N){
//     nx[cnv[i]][0] = nx[cnv[i]][1] = -1;
//     if(i-1 >= 0) nx[cnv[i]][0] = cnv[i-1];
//     if(i+1 <  N) nx[cnv[i]][1] = cnv[i+1];
//   }
// 
//   rep(i,N) ok1.insert(i);
//   rep(i,N) ok2.insert(i);
// 
//   tm = 0;
//   rep(k,Q){
//     tm >?= A[k];
//     while(ok1.size()==0 || (q.size() && -q.top().first <= tm)){
//       tm >?= -q.top().first;
//       i = q.top().second;
//       q.pop();
//       ok1.insert(i);
//       rep(z,3){
//         x = i;
//         if(z < 2) x = nx[i][z];
//         if(x==-1) continue;
//         if(ok1.count(x)==0) continue;
//         if((nx[x][0]==-1 || ok1.count(nx[x][0])==1) && (nx[x][1]==-1 || ok1.count(nx[x][1])==1)) ok2.insert(x);
//       }
//     }
// 
//     if(ok2.size()) i = *ok2.begin();
//     else           i = *ok1.begin();
// 
//     q.push( make_pair(-(tm + B[k]), i) );
// 
//     res[k] = i;
//     ok1.erase(i);
//     rep(z,3){
//       x = i;
//       if(z < 2) x = nx[i][z];
//       if(x==-1) continue;
//       if(ok2.count(x)) ok2.erase(x);
//     }
//   }
// 
//   rep(i,Q) wt(ind[res[i]] + 1);
// }
0