#57201 (C++11) No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ

提出ソース

結果

問題	No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー	たこし
提出日時	2015-11-05 23:42:25
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	5,995 bytes
コンパイル時間	1,222 ms
コンパイル使用メモリ	103,284 KB
実行使用メモリ	47,792 KB
最終ジャッジ日時	2024-09-13 12:54:15
合計ジャッジ時間	10,258 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	AC	30 ms 35,244 KB
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define INF_INT_MAX 2147483647
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
 
using namespace std;

typedef pair<LL, LL> II;

#define MAX_N 300005
#define MAX_Q 150005
#define MAX_T 5
#define MAX_SEG (1 << 17)
#define mod 1000000000000000009

LL N;
int Q;

LL X[MAX_Q], L[MAX_Q], R[MAX_Q];
vector<LL> PosList; //座標圧縮したもの

//ある座標を座標圧縮したものに変換する
int ConvertPos(LL len){
  return lower_bound(PosList.begin(), PosList.end(), len) - PosList.begin();
}

struct Node{
  vector<LL> Score; //今見ているノードの各チームのスコア
  LL Delay[MAX_T]; //遅延値
  bool DelayFlag; //遅延評価を行うかのフラグ
  Node(){
    Score.resize(MAX_T);
    memset(Delay,0,sizeof(Delay));
    DelayFlag = false;
  }
};

int n;
Node seg[2*MAX_SEG - 1];

void Init(int _n){
  n = 1;
  while(n < _n)
    n *= 2;
}

//遅延値の評価
inline void EvaluateDelayValue(int k, int a, int b){

  if(!seg[k].DelayFlag)
    return;

  //問題文にそってスコアを増減させる
  for(int i = 0; i < MAX_T; i++){
    if(seg[k].Delay[i] > 0){
      seg[k].Score[i] += seg[k].Delay[i]*(PosList[b-1] - PosList[a] + 1);
      seg[k].Score[i] %= mod;
    }
    else{
      seg[k].Score[i] = 0;
    }
  }

  //今見ているノードが末端ノードでないときは
  //下の子に遅延を伝播させる
  if(k < n-1){
    int p1 = 2*k+1, p2 = 2*k+2;
    for(int i = 0; i < MAX_T; i++){
      if(seg[k].Delay[i] > 0){
	seg[p1].Delay[i] += seg[k].Delay[i];
	seg[p1].Delay[i] %= mod;
	seg[p2].Delay[i] += seg[k].Delay[i];
	seg[p2].Delay[i] %= mod;
      }
      else{
	seg[p1].Delay[i] = seg[p2].Delay[i] = 0;
      }
    }
    seg[p1].DelayFlag = seg[p2].DelayFlag = true;
  }

  //今見ているノードの遅延値を0にする
  for(int i = 0; i < MAX_T; i++){
    seg[k].Delay[i] = 0;
  }
  seg[k].DelayFlag = false;

}

//k番目のノードの値を更新する
//この関数を使うときは下の子の遅延評価が終わっているときのみ
inline void UpdateNode(int k){
  
  for(int i = 0; i < MAX_T; i++){
    seg[k].Score[i] = seg[2*k+1].Score[i] + seg[2*k+2].Score[i];
  }

}

//[l,r)についてScoreに基づいて色を塗り替える
inline void UpdateRange(int l, int r, vector<LL> Score, int k = 0, int a = 0, int b = n){

  //とりあえず遅延評価
  EvaluateDelayValue(k,a,b);

  //区間が混じっていないなら終了
  if(b <= l || r <= a)
    return;
  //完全に区間が被っている場合
  else if(l <= a && b <= r){
    for(int i = 0; i < MAX_T; i++){
      seg[k].Delay[i] = Score[i];
    }
    seg[k].DelayFlag = true;
    EvaluateDelayValue(k, a, b);
    return;
  }
  //微妙に区間が被っている場合
  else{
    int mid = (a+b)/2;
    UpdateRange(l,r,Score,2*k+1,a,mid);
    UpdateRange(l,r,Score,2*k+2,mid,b);
    UpdateNode(k);
    return;
  }

}

//[l,r)のそれぞれのチームの得点を求める
inline vector<LL> Query(int l, int r, int k = 0, int a = 0, int b = n){
  
  //とりあえず遅延評価
  EvaluateDelayValue(k,a,b);

  vector<LL> ret(5, 0);

  //範囲が被っていない場合
  if(b <= l || r <= a)
    return ret;
  //完全に被っている場合
  else if(l <= a && b <= r){
    return seg[k].Score;
  }
  //微妙に被っている場合
  else{
    vector<LL> p1,p2;
    int mid = (a+b)/2;
    p1 = Query(l,r,2*k+1,a,mid);
    p2 = Query(l,r,2*k+2,mid,b);
    UpdateNode(k);
    for(int i = 0; i < MAX_T; i++){
      ret[i] = p1[i] + p2[i];
      ret[i] %= mod;
    }
    return ret;
  }

  return ret;

}

void DebugSegment(int size = N){

  cerr << "*** Debug Segment ***" << endl;
  for(int i = 0; i < size + n - 1; i++){
    cerr << "seg[" << i << "]" << endl;
    for(int j = 0; j < MAX_T; j++){
      fprintf(stderr, "%d ::  Delay:%lld, Score:%lld\n",j,seg[i].Delay[j],seg[i].Score[j]);
    }
  }
  cerr << endl;

}

int main(){

  cin >> N;
  cin >> Q;
  
  PosList.clear();
  PosList.push_back(0);
  PosList.push_back(N);
  for(int i = 0; i < Q; i++){
    cin >> X[i] >> L[i] >> R[i];
    PosList.push_back(L[i]);
    PosList.push_back(L[i]-1);
    PosList.push_back(L[i]+1);
    PosList.push_back(R[i]);
    PosList.push_back(R[i]-1);
    PosList.push_back(R[i]+1);
  }

  sort(PosList.begin(), PosList.end());
  PosList.erase(unique(PosList.begin(), PosList.end()), PosList.end());

  Init(PosList.size());

  /*
  cerr << "圧縮" << endl;
  for(int i = 0; i < (int)PosList.size(); i++){
    cerr << PosList[i] << endl;
  }
  */

  vector<LL> Ans(5,0);

  //cerr << "*** Query Start ***" << endl;

  for(int q = 0; q < Q; q++){
    
    int posl = ConvertPos(L[q]);
    int posr = ConvertPos(R[q]);
    posr++;
    //ボーナスクエリ
    if(X[q] == 0){
      vector<LL> Score = Query(posl,posr);
      LL m = -1;
      for(int i = 0; i < MAX_T; i++){
	if(m == Score[i]){
	  m = -1;
	  break;
	}
	else if(m < Score[i]){
	  m = Score[i];
	}
      }
      if(m == -1)
	continue;
      else{
	for(int i = 0; i < MAX_T; i++){
	  if(Score[i] == m){
	    Ans[i] += m;
	    Ans[i] %= mod;
	    break;
	  }
	}
      }
    }
    //塗替えクエリ
    else{
      vector<LL> t(5,0);
      t[X[q]-1] = 1;
      UpdateRange(posl, posr, t);
    }

    //DebugSegment(PosList.size());

  }

  vector<LL> t = Query(ConvertPos(0), ConvertPos(N));
  for(int i = 0; i < MAX_T; i++){
    cout << (Ans[i] + t[i]) % mod;
    if(i < MAX_T-1)
      cout << " ";
  }
  cout << endl;

  return 0;

}

yukicoder

結果

テストケース

ソースコード