結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー tone
提出日時 2019-07-30 05:56:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,242 bytes
コンパイル時間 1,034 ms
コンパイル使用メモリ 93,700 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-02 15:35:49
合計ジャッジ時間 4,672 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <bitset>
#include <tuple>
#include <set>
#include <map>
#include <cmath>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi std::vector<std::vector<int> >
#define vvl std::vector<std::vector<ll> >
#define MODs 1000000007;
#define MODn 1000000009;
typedef long long int ll;
using namespace std;

std::vector<std::vector<int> > ss;
std::vector<std::vector<int>  > sec;
int square;
void init(int N, std::vector<int> a){
  square = (int)sqrt(N)+1;
  for(int i=0;i<N/square+(N%square==0?0:1);i++){
    ss.push_back(std::vector<int> {});
  }
  for(int i=0;i<N;i++){
    ss[i/square].push_back(a[i]);
  }
  for(int i=0;i<N/square+(N%square==0?0:1);i++) sec.push_back(std::vector<int> {0, 0, 0});
}
void check(int N){
  for(int i=0;i<N;i++){
    std::cout << ss[i/square][i%square] << ((i+1)%square==0?"\n":" ");
  }
}
void update(int l, int r, int x){
  int left_sec=l/square+(l%square==0?0:1);
  int right_sec=(r+1)/square;
  for(int i=left_sec;i<right_sec;i++){
    sec[i][0] = x;
    sec[i][x] = ss[i].size();
    sec[i][(x==1?2:1)] = 0;
  }
  if(l/square==r/square){
    //same section
    if(sec[l/square][0]!=0){
      for(int i=0;i<ss[l/square].size();i++){
        ss[l/square][i] = sec[l/square][0];
      }
    }
    for(int i=l;i<=r;i++){
      ss[i/square][i%square]=x;
    }
    int o=0,t=0;
    for(int i=0;i<ss[l/square].size();i++){
      if(ss[l/square][i]==1) o++;
      if(ss[l/square][i]==2) t++;
    }
    sec[l/square][0]=0;
    if(o==ss[l/square].size())sec[l/square][0]=1;
    if(t==ss[l/square].size())sec[l/square][0]=2;
    sec[l/square][1]=o;
    sec[l/square][2]=t;
  }else{
    if(sec[l/square][0]!=0){
      for(int i=0;i<ss[l/square].size();i++){
        ss[l/square][i] = sec[l/square][0];
      }
    }
    if(sec[r/square][0]!=0){
      for(int i=0;i<ss[r/square].size();i++){
        ss[r/square][i] = sec[r/square][0];
      }
    }
    for(int i=l;i<ss[l/square].size();i++){
      ss[l/square][i%square]=x;
    }
    for(int i=0;i<=r%square;i++){
      ss[r/square][i%square]=x;
    }
    int o=0,t=0;
    for(int i=0;i<ss[l/square].size();i++){
      if(ss[l/square][i]==1) o++;
      if(ss[l/square][i]==2) t++;
    }
    sec[l/square][0]=0;
    if(o==ss[l/square].size())sec[l/square][0]=1;
    if(t==ss[l/square].size())sec[l/square][0]=2;
    sec[l/square][1]=o;
    sec[l/square][2]=t;

    o=0,t=0;
    for(int i=0;i<ss[r/square].size();i++){
      if(ss[r/square][i]==1) o++;
      if(ss[r/square][i]==2) t++;
    }
    sec[r/square][0]=0;
    if(o==ss[r/square].size())sec[r/square][0]=1;
    if(t==ss[r/square].size())sec[r/square][0]=2;
    sec[r/square][1]=o;
    sec[r/square][2]=t;
  }
}

ll count(int l, int r, int x){
  ll x_count=0;

  if(l/square==r/square){
    if(sec[l/square][0]==0){
      for(int i=l;i<=r;i++){
        if(ss[l/square][i%square]==x) x_count++;
      }
    }else if(sec[l/square][0]==x){
      x_count+=r-l+1;
    }
  }else{
    for(int i=l/square+1;i<r/square;i++){
      if(sec[i][0]==x) x_count += ss[i].size();
      else x_count += sec[i][x];
    }
    if(sec[r/square][0]==0){
      for(int i=0;i<=r%square;i++){
        if(ss[r/square][i]==x) x_count++;
      }
    }else if(sec[r/square][0]==x){
      x_count+=r%square+1;
    }

    if(sec[l/square][0]==0){
      for(int i=l%square;i<ss[l/square].size();i++){
        if(ss[l/square][i]==x) x_count++;
      }
    }else if(sec[l/square][0]==x){
      x_count += ss[l/square].size()-l+1;
    }
  }
  return x_count;
}

int main(int argc, char const *argv[]) {
  int N, Q, x, l, r;
  ll score_A=0, score_B=0;
  std::cin >> N;
  std::cin >> Q;
  std::vector<int> a(N, 0);
  init(N, a);
  for(int i=0;i<Q;i++){
    std::cin >> x >> l >> r;
    if(x==0){
      ll bonus_A = count(l, r, 1);
      ll bonus_B = count(l, r, 2);
      if(bonus_A > bonus_B) score_A+=bonus_A;
      if(bonus_B > bonus_A) score_B+=bonus_B;
    }else{
      update(l, r, x);
    }
  }
  score_A += count(0, N-1, 1);
  score_B += count(0, N-1, 2);
  std::cout << score_A << " " << score_B << '\n';
  return 0;
}
0