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 |
|
|
|
|
|
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 |