| Task: | Simple game |
| Sender: | ArktinenKarpalo |
| Submission time: | 2019-02-10 16:20:53 +0200 |
| Language: | C++ |
| Status: | READY |
| Result: | 22 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 22 |
| #2 | TIME LIMIT EXCEEDED | 0 |
| #3 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.03 s | 1, 3 | details |
| #2 | ACCEPTED | 0.02 s | 1, 3 | details |
| #3 | ACCEPTED | 0.04 s | 1, 3 | details |
| #4 | ACCEPTED | 0.03 s | 1, 3 | details |
| #5 | ACCEPTED | 0.03 s | 1, 3 | details |
| #6 | ACCEPTED | 0.03 s | 1, 3 | details |
| #7 | ACCEPTED | 0.02 s | 1, 2, 3 | details |
| #8 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
| #9 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
| #10 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
| #11 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
| #12 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
| #13 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #14 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #15 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #16 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #17 | TIME LIMIT EXCEEDED | -- | 3 | details |
| #18 | TIME LIMIT EXCEEDED | -- | 2, 3 | details |
Code
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()
using namespace std;
int n, m, h[101010], f, val, pos, kork, sp[1010101*2];
int sum(int a, int b) {
a += 1010101;
b += 1010101;
int ret = 0;
while(a<=b) {
if(a%2==1)
ret += sp[a++];
if(b%2==0)
ret += sp[b--];
a /= 2;
b /= 2;
}
return ret;
}
void add(int k, int x) {
k += 1010101;
sp[k] += x;
while(k>=1) {
sp[k] += x;
k /= 2;
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i=1; i<=n; i++) {
cin >> h[i];
/* if(i > 1) {
if(h[i-1] < h[i]) {
add(h[i-1], 1);
add(h[i], -1);
} else {
}
}*/
}
for(int g=0; g<m; g++) {
cin >> f;
if(f == 1) { // Muuta
cin >> pos >> val;
h[pos] = val;
} else { // Query
cin >> kork;
int ans = 0;
for(int i=2; i<=n; i++) {
if(h[i-1] < h[i]) {
if(h[i-1] <= kork && kork <= h[i])
ans++;
} else {
if(h[i] <= kork && kork <= h[i-1])
ans++;
}
if(h[i] == kork)
ans--;
}
cout << ans << "\n";
}
}
}
Test details
Test 1
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 3 3 1 5 1 2 3 1 1 5 2 3 |
| correct output |
|---|
| 2 1 |
| user output |
|---|
| 2 1 |
Test 2
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 403944 539844 451514 488113 69... |
| correct output |
|---|
| 444 462 34 516 288 ... |
| user output |
|---|
| 444 462 34 516 288 ... Truncated |
Test 3
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 487368 55984 456259 117591 818... |
| correct output |
|---|
| 440 400 480 130 38 ... |
| user output |
|---|
| 440 400 480 130 38 ... Truncated |
Test 4
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 570792 604828 236813 971260 13... |
| correct output |
|---|
| 386 460 50 470 126 ... |
| user output |
|---|
| 386 460 50 470 126 ... Truncated |
Test 5
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 686920 120969 241559 600738 48... |
| correct output |
|---|
| 330 306 418 290 136 ... |
| user output |
|---|
| 330 306 418 290 136 ... Truncated |
Test 6
Group: 1, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 737640 478325 54816 262919 609... |
| correct output |
|---|
| 230 418 148 338 4 ... |
| user output |
|---|
| 230 418 148 338 4 ... Truncated |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
| input |
|---|
| 1000 1000 1 1000000 1 1000000 1 1000000 ... |
| correct output |
|---|
| 999 999 999 999 999 ... |
| user output |
|---|
| 999 999 999 999 999 ... Truncated |
Test 8
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 18 15 8 5 7 19 19 11 11 8 6 15... |
| correct output |
|---|
| 0 0 0 0 0 ... |
| user output |
|---|
| (empty) |
Test 9
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 611680 625326 848926 304761 34... |
| correct output |
|---|
| 30636 30745 50130 4464 9086 ... |
| user output |
|---|
| (empty) |
Test 10
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 695104 174171 853672 901534 35... |
| correct output |
|---|
| 31870 39772 30788 11144 42732 ... |
| user output |
|---|
| (empty) |
Test 11
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 1 1 1 2 1 1 2 1 2 2 1 2 2 1 1 ... |
| correct output |
|---|
| 0 0 0 0 0 ... |
| user output |
|---|
| (empty) |
Test 12
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 2845 22894 4105 11830 29440 21... |
| correct output |
|---|
| 45066 50090 24109 27778 294 ... |
| user output |
|---|
| (empty) |
Test 13
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 123269 247698 241557 639404 38... |
| correct output |
|---|
| 37412 1520 46224 964 50058 ... |
| user output |
|---|
| (empty) |
Test 14
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 206693 572351 22110 493074 737... |
| correct output |
|---|
| 33086 49042 43971 17756 41889 ... |
| user output |
|---|
| (empty) |
Test 15
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 322821 121195 59560 155256 829... |
| correct output |
|---|
| 28252 45031 28212 6208 31642 ... |
| user output |
|---|
| (empty) |
Test 16
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 438949 637336 872818 784733 17... |
| correct output |
|---|
| 45374 22320 9690 5630 40012 ... |
| user output |
|---|
| (empty) |
Test 17
Group: 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 489669 186180 653371 446915 52... |
| correct output |
|---|
| 43104 43128 41430 35554 996 ... |
| user output |
|---|
| (empty) |
Test 18
Group: 2, 3
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 100000 1 1000000 1 1000000 1 1000000 ... |
| correct output |
|---|
| 99999 99999 99999 99999 99999 ... |
| user output |
|---|
| (empty) |