Submission #1612840


Source Code Expand

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const LD PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

/*
thx
https://ideone.com/Kn5ypG
https://www.slideshare.net/chokudai/square869120-contest2s
*/
int seg[262144][2];//262144=2^18

//範囲[a,b)をビット反転する処理
//[a,b)を調べてる。
//今見ている範囲は[L,R)
//k:ノード番号的な
void query1(int a,int b,int k,int L,int R){
	if( R <= a || b <= L ) return;//範囲外
	if( a <= L && R <= b ){
		//調べたい範囲がすべて収まっている。
		int p = k;
		int d = R-L;
		seg[k][0] = (R-L) - seg[k][0];//範囲内の1の数を更新
		seg[k][1]++;//反転回数を1増やす

		//上に伝播
		while( p > 1){
			p >>= 1;//上に行く
			d <<= 1;//上に行くにつれ範囲が2倍(仕様)
			seg[p][0] = seg[2*p][0] + seg[2*p+1][0];//子の和
			if( seg[p][1] % 2 == 1 ){//反転回数が奇数なら反転
				seg[p][0] = d - seg[p][0];
			}
		}
	}else{//調べる範囲の分割
		//下に任せる
		query1(a,b,2*k+0, L,(L+R)/2 );
		query1(a,b,2*k+1, (L+R)/2,R);
	}
}

//範囲[a,b)にある1の総数
int query2(int a,int b,int k,int L,int R){
	if( R <= a || b <= L ) return 0;//範囲外
	if( a <= L && R <= b ){
		//すべて範囲内
		int ret = seg[k][0];
		int p = k;
		
		//上に上って、反転回数を見る
		while(p>1){
			p >>= 1;
			if( seg[p][1] % 2 == 1 ){
				ret = (R-L) - ret;
			}
		}
		return ret;
	}
	{
		//範囲の分割
		int Lc = query2(a,b,2*k+0,L,(L+R)/2);
		int Rc = query2(a,b,2*k+1,(L+R)/2,R);
		return Lc+Rc;
	}
}

void solve(){
	int N,Q,c,lp,rp;
	cin >> N >> Q;

	while(Q--){
		cin >> c >> lp >> rp;
		if( c == 1 ){
			query1(lp,rp,1,0,N+1);
		}else{
			int res = query2(lp,rp,1,0,N+1);
			cout << res << endl;
		}
	}
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Submission Info

Submission Time
Task H - Counting 1's
User akarin55
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3020 Byte
Status WA
Exec Time 192 ms
Memory 2560 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 0 / 4 0 / 12 0 / 36 0 / 48
Status
AC × 3
AC × 4
WA × 8
AC × 3
WA × 3
AC × 3
WA × 3
AC × 4
WA × 17
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
Subtask1 sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt
Subtask3 sample_1.txt, sample_2.txt, sample_3.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub4_1.txt, sub4_2.txt, sub4_3.txt
Case Name Status Exec Time Memory
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sub1_1.txt WA 1 ms 256 KB
sub1_2.txt AC 1 ms 256 KB
sub1_3.txt WA 1 ms 256 KB
sub1_4.txt WA 3 ms 384 KB
sub1_5.txt WA 2 ms 256 KB
sub1_6.txt WA 1 ms 384 KB
sub1_7.txt WA 5 ms 384 KB
sub1_8.txt WA 8 ms 384 KB
sub1_9.txt WA 8 ms 384 KB
sub2_1.txt WA 133 ms 2304 KB
sub2_2.txt WA 135 ms 2304 KB
sub2_3.txt WA 137 ms 2304 KB
sub3_1.txt WA 174 ms 2560 KB
sub3_2.txt WA 175 ms 2560 KB
sub3_3.txt WA 175 ms 2560 KB
sub4_1.txt WA 192 ms 2560 KB
sub4_2.txt WA 189 ms 2560 KB
sub4_3.txt WA 186 ms 2560 KB