| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55396 |
2018-07-07T07:29:18 Z |
윤교준(#1546) |
Employment (JOI16_employment) |
C++11 |
|
530 ms |
10928 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[sz(V)-2])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const int MAXN = 200005;
const int MAXQ = 200005;
const int MX = 524288;
struct BIT {
int d[MX*2];
void upd(int x, int r) {
for(x += MX; x; x /= 2) d[x] += r;
}
int get(int s, int e) {
int r = 0; for(s += MX, e += MX; s <= e; s /= 2, e /= 2) {
if(s&1) r += d[s++]; if(~e&1) r += d[e--];
} return r;
}
int get(int x) { return get(x, MX-1); }
} segV, segE;
int A[MAXN];
int B[MAXQ], C[MAXQ], D[MAXQ];
int N, Q;
int main() {
ios::sync_with_stdio(false);
cin >> N >> Q;
for(int i = 1; i <= N; i++) cin >> A[i];
for(int i = 1; i <= Q; i++) {
cin >> B[i] >> C[i];
if(2 == B[i]) cin >> D[i];
}
{
vector<int> V;
for(int i = 1; i <= N; i++) V.pb(A[i]);
for(int i = 1; i <= Q; i++)
V.pb(1 == B[i] ? C[i] : D[i]);
sorv(V); univ(V);
for(int i = 1; i <= N; i++)
A[i] = (int)(lower_bound(allv(V), A[i]) - V.begin()) + 1;
for(int i = 1; i <= Q; i++) {
if(1 == B[i])
C[i] = (int)(lower_bound(allv(V), C[i]) - V.begin()) + 1;
else
D[i] = (int)(lower_bound(allv(V), D[i]) - V.begin()) + 1;
}
}
for(int i = 1; i <= N; i++) {
segV.upd(A[i], 1);
if(1 < i && A[i] <= A[i-1]) segE.upd(A[i], 1);
if(i < N && A[i] < A[i+1]) segE.upd(A[i], 1);
}
for(int qi = 1; qi <= Q; qi++) {
if(1 == B[qi]) {
printf("%d\n", segV.get(C[qi]) - segE.get(C[qi]));
} else {
int x = C[qi], y = D[qi];
{
segV.upd(A[x], -1);
if(1 < x && A[x] <= A[x-1]) segE.upd(A[x], -1);
if(x < N && A[x] < A[x+1]) segE.upd(A[x], -1);
if(1 < x && A[x-1] < A[x]) segE.upd(A[x-1], -1);
if(x < N && A[x+1] <= A[x]) segE.upd(A[x+1], -1);
}
{
A[x] = y;
segV.upd(y, 1);
if(1 < x && A[x] <= A[x-1]) segE.upd(A[x], 1);
if(x < N && A[x] < A[x+1]) segE.upd(A[x], 1);
if(1 < x && A[x-1] < A[x]) segE.upd(A[x-1], 1);
if(x < N && A[x+1] <= A[x]) segE.upd(A[x+1], 1);
}
}
}
return 0;
}
Compilation message
employment.cpp: In member function 'int BIT::get(int, int)':
employment.cpp:35:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if(s&1) r += d[s++]; if(~e&1) r += d[e--];
^~
employment.cpp:35:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
if(s&1) r += d[s++]; if(~e&1) r += d[e--];
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
688 KB |
Output is correct |
| 4 |
Correct |
3 ms |
688 KB |
Output is correct |
| 5 |
Correct |
2 ms |
688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
724 KB |
Output is correct |
| 7 |
Correct |
4 ms |
784 KB |
Output is correct |
| 8 |
Correct |
3 ms |
936 KB |
Output is correct |
| 9 |
Correct |
4 ms |
936 KB |
Output is correct |
| 10 |
Correct |
4 ms |
936 KB |
Output is correct |
| 11 |
Correct |
4 ms |
936 KB |
Output is correct |
| 12 |
Correct |
4 ms |
936 KB |
Output is correct |
| 13 |
Correct |
5 ms |
936 KB |
Output is correct |
| 14 |
Correct |
6 ms |
936 KB |
Output is correct |
| 15 |
Correct |
5 ms |
936 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
936 KB |
Output is correct |
| 2 |
Correct |
5 ms |
936 KB |
Output is correct |
| 3 |
Correct |
5 ms |
936 KB |
Output is correct |
| 4 |
Correct |
23 ms |
1548 KB |
Output is correct |
| 5 |
Correct |
49 ms |
2324 KB |
Output is correct |
| 6 |
Correct |
64 ms |
3228 KB |
Output is correct |
| 7 |
Correct |
167 ms |
4452 KB |
Output is correct |
| 8 |
Correct |
146 ms |
5376 KB |
Output is correct |
| 9 |
Correct |
293 ms |
8616 KB |
Output is correct |
| 10 |
Correct |
259 ms |
8616 KB |
Output is correct |
| 11 |
Correct |
341 ms |
9544 KB |
Output is correct |
| 12 |
Correct |
372 ms |
10528 KB |
Output is correct |
| 13 |
Correct |
365 ms |
10528 KB |
Output is correct |
| 14 |
Correct |
392 ms |
10528 KB |
Output is correct |
| 15 |
Correct |
362 ms |
10528 KB |
Output is correct |
| 16 |
Correct |
410 ms |
10604 KB |
Output is correct |
| 17 |
Correct |
407 ms |
10692 KB |
Output is correct |
| 18 |
Correct |
402 ms |
10692 KB |
Output is correct |
| 19 |
Correct |
371 ms |
10692 KB |
Output is correct |
| 20 |
Correct |
379 ms |
10692 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
484 KB |
Output is correct |
| 3 |
Correct |
2 ms |
688 KB |
Output is correct |
| 4 |
Correct |
3 ms |
688 KB |
Output is correct |
| 5 |
Correct |
2 ms |
688 KB |
Output is correct |
| 6 |
Correct |
2 ms |
724 KB |
Output is correct |
| 7 |
Correct |
4 ms |
784 KB |
Output is correct |
| 8 |
Correct |
3 ms |
936 KB |
Output is correct |
| 9 |
Correct |
4 ms |
936 KB |
Output is correct |
| 10 |
Correct |
4 ms |
936 KB |
Output is correct |
| 11 |
Correct |
4 ms |
936 KB |
Output is correct |
| 12 |
Correct |
4 ms |
936 KB |
Output is correct |
| 13 |
Correct |
5 ms |
936 KB |
Output is correct |
| 14 |
Correct |
6 ms |
936 KB |
Output is correct |
| 15 |
Correct |
5 ms |
936 KB |
Output is correct |
| 16 |
Correct |
4 ms |
936 KB |
Output is correct |
| 17 |
Correct |
5 ms |
936 KB |
Output is correct |
| 18 |
Correct |
5 ms |
936 KB |
Output is correct |
| 19 |
Correct |
23 ms |
1548 KB |
Output is correct |
| 20 |
Correct |
49 ms |
2324 KB |
Output is correct |
| 21 |
Correct |
64 ms |
3228 KB |
Output is correct |
| 22 |
Correct |
167 ms |
4452 KB |
Output is correct |
| 23 |
Correct |
146 ms |
5376 KB |
Output is correct |
| 24 |
Correct |
293 ms |
8616 KB |
Output is correct |
| 25 |
Correct |
259 ms |
8616 KB |
Output is correct |
| 26 |
Correct |
341 ms |
9544 KB |
Output is correct |
| 27 |
Correct |
372 ms |
10528 KB |
Output is correct |
| 28 |
Correct |
365 ms |
10528 KB |
Output is correct |
| 29 |
Correct |
392 ms |
10528 KB |
Output is correct |
| 30 |
Correct |
362 ms |
10528 KB |
Output is correct |
| 31 |
Correct |
410 ms |
10604 KB |
Output is correct |
| 32 |
Correct |
407 ms |
10692 KB |
Output is correct |
| 33 |
Correct |
402 ms |
10692 KB |
Output is correct |
| 34 |
Correct |
371 ms |
10692 KB |
Output is correct |
| 35 |
Correct |
379 ms |
10692 KB |
Output is correct |
| 36 |
Correct |
7 ms |
10692 KB |
Output is correct |
| 37 |
Correct |
4 ms |
10692 KB |
Output is correct |
| 38 |
Correct |
5 ms |
10692 KB |
Output is correct |
| 39 |
Correct |
20 ms |
10692 KB |
Output is correct |
| 40 |
Correct |
38 ms |
10692 KB |
Output is correct |
| 41 |
Correct |
73 ms |
10692 KB |
Output is correct |
| 42 |
Correct |
126 ms |
10692 KB |
Output is correct |
| 43 |
Correct |
183 ms |
10692 KB |
Output is correct |
| 44 |
Correct |
341 ms |
10692 KB |
Output is correct |
| 45 |
Correct |
212 ms |
10692 KB |
Output is correct |
| 46 |
Correct |
303 ms |
10692 KB |
Output is correct |
| 47 |
Correct |
404 ms |
10692 KB |
Output is correct |
| 48 |
Correct |
420 ms |
10772 KB |
Output is correct |
| 49 |
Correct |
436 ms |
10772 KB |
Output is correct |
| 50 |
Correct |
416 ms |
10772 KB |
Output is correct |
| 51 |
Correct |
335 ms |
10772 KB |
Output is correct |
| 52 |
Correct |
336 ms |
10836 KB |
Output is correct |
| 53 |
Correct |
339 ms |
10880 KB |
Output is correct |
| 54 |
Correct |
444 ms |
10928 KB |
Output is correct |
| 55 |
Correct |
530 ms |
10928 KB |
Output is correct |
