結果

問題 No.619 CardShuffle
ユーザー Sebastian KingSebastian King
提出日時 2017-12-19 19:04:04
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 100 ms / 3,000 ms
コード長 2,902 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 161,040 KB
実行使用メモリ 12,748 KB
最終ジャッジ日時 2024-06-02 05:05:56
合計ジャッジ時間 4,490 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,944 KB
testcase_13 AC 1 ms
6,944 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 93 ms
11,596 KB
testcase_17 AC 81 ms
11,084 KB
testcase_18 AC 92 ms
12,488 KB
testcase_19 AC 78 ms
9,676 KB
testcase_20 AC 82 ms
10,956 KB
testcase_21 AC 87 ms
11,592 KB
testcase_22 AC 68 ms
12,748 KB
testcase_23 AC 88 ms
12,488 KB
testcase_24 AC 67 ms
9,804 KB
testcase_25 AC 66 ms
9,804 KB
testcase_26 AC 100 ms
9,676 KB
testcase_27 AC 93 ms
11,340 KB
testcase_28 AC 99 ms
11,344 KB
testcase_29 AC 91 ms
12,232 KB
testcase_30 AC 88 ms
12,492 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 78 ms
11,340 KB
testcase_33 AC 91 ms
12,364 KB
testcase_34 AC 87 ms
11,340 KB
testcase_35 AC 37 ms
6,944 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:106:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  106 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:108:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  108 |                 scanf("%s", s);
      |                 ~~~~~^~~~~~~~~
main.cpp:128:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
main.cpp:131:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  131 |                 scanf("%s", s);
      |                 ~~~~~^~~~~~~~~
main.cpp:132:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  132 |                 scanf("%d%d", &x, &y);
      |                 ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MM = 1e9 + 7;
const int MAXN = 2e6 + 10;

int n, m, M, Q;
char s[100];
ll a[MAXN];
int L[MAXN], R[MAXN];

const int MAKI = 9;

struct node{
	int tp, nxt;
	ll a, b, c;
} rst[MAXN], nico;

void merge(node &ru, node rl, node rr){
	ru.nxt = rr.nxt;
	if (rl.tp == 1){
		if (rr.tp == 1){
			if (rl.nxt == -2){
				ru.tp = 1;
				ru.a = rl.a * rr.a % MM;
			}
			else{
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = 0;
				ru.c = rr.a;
			}
		}
		else{
			if (rl.nxt == -2){
				ru.tp = 2;
				ru.a = rl.a * rr.a % MM;
				ru.b = rr.b;
				ru.c = rr.c;
			}
			else{
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = rr.a + rr.b;
				ru.c = rr.c;
			}
		}
	}
	else{
		if (rr.tp == 1){
			if (rl.nxt == -2){
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = rl.b;
				ru.c = rl.c * rr.a % MM;
			}
			else{
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = rl.b + rl.c;
				ru.c = rr.a;
			}
		}
		else{
			if (rl.nxt == -2){
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = (rl.b + rl.c * rr.a + rr.b) % MM;
				ru.c = rr.c;
			}
			else{
				ru.tp = 2;
				ru.a = rl.a;
				ru.b = (rl.b + rl.c + rr.a + rr.b) % MM;
				ru.c = rr.c;
			}
		}
	}
}

void update(int u){
	int l = u << 1;
	int r = l | 1;
	merge(rst[u], rst[l], rst[r]);
}

node query(int u, int L, int R, int l, int r){
	if (L == l && R == r)
		return rst[u];
	int m = (L + R) / 2;
	if (r <= m)
		return query(u * 2, L, m, l, r);
	else if (l > m)
		return query(u * 2 + 1, m + 1, R, l, r);
	else{
		node f;
		merge(f, query(u*2,L,m,l,m), query(u*2+1,m+1,R,m+1,r));
		return f;
	}
}

int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		scanf("%s", s);
		if (s[0] == '+') a[i] = -1;
		else if (s[0] == '*') a[i] = -2;
		else a[i] = s[0] - '0';
	}
	a[++n] = -1;
	for(M=1;M<n;M*=2);
	for (int i = n + 1; i < M; i += 2){
		a[i] = 0;
		a[i + 1] = -1;
	}
	M /= 2;
	for (int i = 1; i <= M; i++){
		rst[i + M - 1].tp = 1;
		rst[i + M - 1].a = a[i * 2 - 1];
		rst[i + M - 1].nxt = a[i * 2];
	}
	for (int i = M - 1; i >= 1; i--){
		update(i);
	}
	scanf("%d", &Q);
	while(Q--){
		int x, y;
		scanf("%s", s);
		scanf("%d%d", &x, &y);
		if (s[0] == '?'){
			nico = query(1, 1, M, (x+1)/2, (y+1)/2);
			if (nico.tp == 1) printf("%lld\n", nico.a);
			else printf("%lld\n", (nico.a+nico.b+nico.c)%MM);
		}
		else{
			swap(a[x], a[y]);
			if(x&1)rst[(x+1)/2+M-1].a=a[x];else rst[(x+1)/2+M-1].nxt=a[x];
			for (int i = ((x+1)/2+M-1)/2; i >= 1; i /= 2) update(i);
			if(y&1)rst[(y+1)/2+M-1].a=a[y];else rst[(y+1)/2+M-1].nxt=a[y];
			for (int i = ((y+1)/2+M-1)/2; i >= 1; i /= 2) update(i);
			/*
			puts("==================");
			printf("%s   %d   %d\n", s, x, y);
			for (int l = 1, r = 1; l <= M; l = r + 1, r = l * 2 - 1){
				for (int i = l; i <= r; i++){
					printf("[%d %d %lld %lld %lld], ", rst[i].tp, rst[i].nxt, rst[i].a, rst[i].b, rst[i].c);
				}
				puts("");
			}
			*/
		}
	}
	return 0;
}
0