結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー tubo28tubo28
提出日時 2015-06-19 23:24:23
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 4,934 bytes
コンパイル時間 1,516 ms
コンパイル使用メモリ 148,720 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-21 10:13:33
合計ジャッジ時間 4,541 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#define _CRT_SECURE_NO_WARNINGS
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
//#define endl "\n"
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator<<(ostream & os, vector<T> const &);
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream & os, tuple<T...> const & t){ _ot<0>(os, t); return os; }
template<class T, class U> ostream & operator<<(ostream & os, pair<T,U> const & p){ return os << "(" << p.first << ", " << p.second << ") "; }
template<class T> ostream & operator<<(ostream & os, vector<T> const & v){ rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os; }
template<class T> inline bool chmax(T & x, T const & y){ return x<y ? x=y,true : false; }
template<class T> inline bool chmin(T & x, T const & y){ return x>y ? x=y,true : false; }
#ifdef DEBUG
#define dump(...) (cerr<<#__VA_ARGS__<<" = "<<mt(__VA_ARGS__)<<" ["<<__LINE__<<"]"<<endl)
#else
#define dump(...)
#endif
// ll const mod = 1000000007;
// ll const inf = 1LL<<60;

/*
  セグメント木
  コンストラクタには要素数を渡す
  * 根 : 1
  * 左からx番目の葉 : x+N
  * iの親のindex : i/2
  * iの子のindex : i*2+0, i*2+1
  * iの兄弟(sibling) : i^1
  * iの深さ(depth) : log_2 iの整数部分
  * iの区間幅(width) : N/highest(i)
  * iの区間の左端 : (i-highest(i))*width(i)
  */

typedef ll dat_t;
dat_t const init = 0;
struct Segtree {
    vector<dat_t> partial, overall;
    int n;
    Segtree(int n_){
        n = 1;
        while(n < n_) n<<=1;
        partial.assign(n+n,0);
        overall.assign(n+n,0);
    }

    void add(int a, int b, int x, int k, int l, int r){
        if(a <= l && r <= b){
            partial[k] += x;
        } else if(l < b && a < r){
            overall[k] += (min(b,r)-max(a,l)) * x;
            add(a,b,x,k<<1,l,(l+r)/2);
            add(a,b,x,k<<1|1,(l+r)/2,r);
        }
    }
    void add(int a, int b, int x){
        add(a,b,x,1,0,n);
    }

    dat_t sum(int a, int b, int k, int l, int r){
        if(b <= l || r <= a){
            return 0;
        } else if(a <= l && r <= b){
            return partial[k]*(r-l) + overall[k];
        } else {
            dat_t res = (min(b,r)-max(a,l)) * partial[k];
            res += sum(a,b,k<<1,l,(l+r)/2);
            res += sum(a,b,k<<1|1,(l+r)/2,r);
            return res;
        }
    }
    dat_t sum(int a, int b){
        return sum(a,b,1,0,n);
    }
};

// Segtree(size)
// add(l,r,val)
// sum(l,r)

// 区間全体をある値にセット
// 区間全体を

typedef unsigned long long ull;
ull A[2000], B[2000];

ull M1[100], M2[100];
int PC[70000];

inline int cnt(int l, int r, ull * A){
    if(l/64 != r/64){
        int res = 0;
        res += PC[M2[64-l%64] & A[l/64]];
        res += PC[M1[r%64] & A[r/64]];
        loop(i,l/64+1,r/64) res += PC[A[i]];
        return res;
    } else {
        int res = 0;
        loop(i,l,r) res += !!(A[i/64] & (1 << (i%64)));
        return res;
    }
}

inline void zero(int l, int r, ull * A){
    if(l/64 != r/64){
        A[l/64] &= ~M2[64-l%64];
        A[r/64] &= ~M1[r%64];
        loop(i,l/64+1,r/64) A[i] = 0;
    } else {
        loop(i,l,r) A[i/64] &= ~(1ULL << (i%64));
    }
}

inline void one(int l, int r, ull * A){
    if(l/64 != r/64){
        A[l/64] |= M2[64-l%64];
        A[r/64] |= M1[r%64];
        loop(i,l/64+1,r/64) A[i] = ~0ULL;
    } else {
        loop(i,l,r) A[i/64] |= 1ULL << (i%64);
    }
}

int main(){
    int N;
    while(cin >> N){
        rep(i,65536) PC[i] = PC[i>>1] + (i&1);
        memset(A,0,sizeof(A));
        memset(B,0,sizeof(B));
        M1[0] = 0;
        M2[0] = 0;
        rep(i,63) M1[i+1] = (M1[i]<<1) | 1, M2[i+1] = (M2[i]>>1) | (1ULL<<63);
        int Q;
        cin >> Q;
        int ca = 0, cb = 0;
        rep(i,Q){
            int x,l,r;
            scanf("%d%d%d",&x,&l,&r);
            r++;
            if(x==0){
                int a = cnt(l,r,A);
                int b = cnt(l,r,B);
                if(a > b){
                    ca += a;
                } else if(a < b){
                    cb += b;
                }
            } else if(x==1){
                one(l,r,A);
                zero(l,r,B);
            } else {
                one(l,r,B);
                zero(l,r,A);
            }
        }
        ca += cnt(0,N+10,A);
        cb += cnt(0,N+10,B);
        printf("%d %d\n",ca,cb);
    }
}
0