結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー たこし
提出日時 2015-11-05 23:42:25
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 RE * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0