結果

問題 No.619 CardShuffle
ユーザー Sebastian KingSebastian King
提出日時 2017-12-19 19:00:33
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,896 bytes
コンパイル時間 1,580 ms
コンパイル使用メモリ 146,532 KB
実行使用メモリ 5,840 KB
最終ジャッジ日時 2023-08-24 14:55:22
合計ジャッジ時間 6,969 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,616 KB
testcase_01 AC 2 ms
5,616 KB
testcase_02 AC 2 ms
5,780 KB
testcase_03 AC 2 ms
5,612 KB
testcase_04 AC 2 ms
5,540 KB
testcase_05 AC 3 ms
5,516 KB
testcase_06 AC 2 ms
5,624 KB
testcase_07 AC 2 ms
5,564 KB
testcase_08 AC 2 ms
5,740 KB
testcase_09 AC 2 ms
5,584 KB
testcase_10 AC 2 ms
5,740 KB
testcase_11 AC 2 ms
5,840 KB
testcase_12 AC 2 ms
5,720 KB
testcase_13 AC 2 ms
5,588 KB
testcase_14 AC 2 ms
5,616 KB
testcase_15 AC 2 ms
5,544 KB
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

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