結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー tonetone
提出日時 2019-07-30 06:15:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,160 bytes
コンパイル時間 841 ms
コンパイル使用メモリ 93,564 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-02 15:36:13
合計ジャッジ時間 3,392 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 255 ms
5,376 KB
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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){
  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++;
    }
    if(o==ss[l/square].size()) sec[l/square][0]=1;
    if(t==ss[l/square].size()) sec[l/square][0]=2;
    else sec[l/square][0]=0;
    sec[l/square][1]=o;
    sec[l/square][2]=t;
  }else{
    for(int i=l/square+1;i<r/square;i++){
      sec[i][0] = x;
      sec[i][x] = ss[i].size();
      sec[i][(x==1?2:1)] = 0;
    }
    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%square;i<ss[l/square].size();i++) ss[l/square][i]=x;
    for(int i=0;i<=r%square;i++) ss[r/square][i]=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++;
    }
    if(o==ss[l/square].size())sec[l/square][0]=1;
    else if(t==ss[l/square].size())sec[l/square][0]=2;
    else sec[l/square][0]=0;
    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++;
    }
    if(o==ss[r/square].size())sec[r/square][0]=1;
    else if(t==ss[r/square].size())sec[r/square][0]=2;
    else sec[r/square][0]=0;
    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