結果

問題 No.619 CardShuffle
コンテスト
ユーザー Sebastian King
提出日時 2017-12-19 19:04:04
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 115 ms / 3,000 ms
コード長 2,902 bytes
コンパイル時間 1,319 ms
コンパイル使用メモリ 160,832 KB
実行使用メモリ 8,832 KB
最終ジャッジ日時 2024-12-22 22:36:54
合計ジャッジ時間 4,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 #
raw source code 

#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