Kyselyt

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define ll long long
#define N (2<<16)

using namespace std;

long v[2*N];
long m[2*N];

void c (int k, long a) {
	k += N;
	v[k] = a;
	//cout<<"foo: "<<k<<endl;
	m[k] = a;
	for (k /= 2; k > 0; k /= 2) {
		v[k] = v[2*k] + v[2*k+1];
		m[k] = min(m[2*k], v[2*k+1]);
	}
}

void qu (long a, long b) {
	a += N;
	b += N;
	long w = (b - a + 1);
	long s = 0;
	long mn = 100000;
	while (a <= b) {
		if (a % 2 == 1) {
			mn = min(mn, m[a]);
			s += v[a++];
		}
		if (b % 2 == 0) {
			mn = min(mn, m[b]);
			s += v[b--];
		}
		a /= 2;
		b /= 2;
	}

	s -= (mn - 1) * w;
	//cout<<s<<" "<<(w * (w + 1) / 2)<<endl;
	if (s == (w * (w + 1) / 2)) cout<<"10-4"<<endl;
	else cout<<"QAQ"<<endl;
}

int main () {
	int n, q;
	cin>>n>>q;
	if (n > 1000 || q > 1000) {
		for (int i = 0; i < n; i++) {
			int k;
			cin>>k;
			c(i + 1, k);
		}
		for (int i = 0; i < q; i++) {
			char x;
			cin>>x;
			int a, b;
			cin>>a>>b;
			//a--; b--;
			if (x == '!') {
				long l = v[a + N];
				//cout<<l<<" "<<(a + N)<<":"<<v[b + N]<<" "<<(b + N)<<endl;
				c(a, v[b + N]);
				c(b, l);
			} else {
				qu(a, b);
			}
		}
	} else {
		int e[n];
		for (int i = 0; i < n; i++) cin>>e[i];
		for (int i = 0; i < q; i++) {
			char c;			
			cin>>c;
			int a, b;
			cin>>a>>b;
			set<int> s;
			for (int x = a - 1; x < b; x++) {
				s.insert(e[x]);
				if (*s.end() - *s.begin() == b - a) cout<<"10-4"<<endl;
				else cout<<"QAQ"<<endl;
			}
		}
	}
}

Test 1

Group: 1

Verdict: WRONG ANSWER

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED