oj.uz

Submission #55359

# Submission time Handle Problem Language Result Execution time Memory
55359 2018-07-07T05:22:05 Z 김세빈(#1545) Employment (JOI16_employment) C++11
100 / 100
 775 ms 240684 KB 
#include <bits/stdc++.h>

using namespace std;

struct node{
	int l, r, v;
	node() { l = r = v = 0; }
};

node T[20202020];
int K[202020], A[202020];
int n, m, t;

int update(int p)
{
	int a = K[p];
	
	if(A[p] >= A[p-1] && A[p] > A[p+1]) K[p] = 1;
	else if(A[p] < A[p-1] && A[p] <= A[p+1]) K[p] = -1;
	else K[p] = 0;
	
	return K[p] - a;
}

void insert(int p, int s, int e, int v, int c)
{
	T[p].v += c;
	if(s == e) return;
	
	if(v <= (s+e>>1)){
		if(!T[p].l) T[p].l = ++t;
		insert(T[p].l, s, s+e>>1, v, c);
	}
	else{
		if(!T[p].r) T[p].r = ++t;
		insert(T[p].r, (s+e>>1)+1, e, v, c);
	}
}

int get_sum(int p, int s, int e, int l, int r)
{
	if(!p || e < l || r < s) return 0;
	if(l <= s && e <= r) return T[p].v;
	
	return get_sum(T[p].l, s, s+e>>1, l, r) + get_sum(T[p].r, (s+e>>1)+1, e, l, r);
}

int main()
{
	int i, k, a, b;
	
	scanf("%d%d", &n, &m);
	
	A[0] = A[n+1] = -1e9;
	t = 1;
	
	for(i=1;i<=n;i++){
		scanf("%d", A+i);
	}
	
	for(i=1;i<=n;i++){
		insert(1, 1, 1e9, A[i], update(i));
	}
	
	for(i=0;i<m;i++){
		scanf("%d", &a);
		if(a == 1){
			scanf("%d", &a);
			printf("%d\n", get_sum(1, 1, 1e9, a, 1e9));
		}
		else{
			scanf("%d", &k);
			insert(1, 1, 1e9, A[k], -K[k]); K[k] = 0;
			scanf("%d", A+k);
			insert(1, 1, 1e9, A[k], update(k));
			if(k > 1) insert(1, 1, 1e9, A[k-1], update(k-1));
			if(k < n) insert(1, 1, 1e9, A[k+1], update(k+1));
		}
	}
	
	return 0;
}

Compilation message

employment.cpp: In function 'void insert(int, int, int, int, int)':
employment.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)){
           ~^~
employment.cpp:32:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].l, s, s+e>>1, v, c);
                     ~^~
employment.cpp:36:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   insert(T[p].r, (s+e>>1)+1, e, v, c);
                   ~^~
employment.cpp: In function 'int get_sum(int, int, int, int, int)':
employment.cpp:45:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return get_sum(T[p].l, s, s+e>>1, l, r) + get_sum(T[p].r, (s+e>>1)+1, e, l, r);
                            ~^~
employment.cpp:45:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  return get_sum(T[p].l, s, s+e>>1, l, r) + get_sum(T[p].r, (s+e>>1)+1, e, l, r);
                                                             ~^~
employment.cpp: In function 'int main()':
employment.cpp:50:15: warning: unused variable 'b' [-Wunused-variable]
  int i, k, a, b;
               ^
employment.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
employment.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
employment.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
employment.cpp:72:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~
employment.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", A+k);
    ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 237560 KB Output is correct
2 Correct 188 ms 237564 KB Output is correct
3 Correct 183 ms 237708 KB Output is correct
4 Correct 185 ms 237708 KB Output is correct
5 Correct 184 ms 237708 KB Output is correct
6 Correct 183 ms 237756 KB Output is correct
7 Correct 183 ms 237756 KB Output is correct
8 Correct 191 ms 237756 KB Output is correct
9 Correct 194 ms 237756 KB Output is correct
10 Correct 187 ms 237788 KB Output is correct
11 Correct 187 ms 237860 KB Output is correct
12 Correct 191 ms 237860 KB Output is correct
13 Correct 187 ms 237884 KB Output is correct
14 Correct 185 ms 237884 KB Output is correct
15 Correct 191 ms 237884 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 237884 KB Output is correct
2 Correct 187 ms 237892 KB Output is correct
3 Correct 193 ms 237892 KB Output is correct
4 Correct 220 ms 237976 KB Output is correct
5 Correct 236 ms 238328 KB Output is correct
6 Correct 264 ms 238368 KB Output is correct
7 Correct 265 ms 238748 KB Output is correct
8 Correct 320 ms 239260 KB Output is correct
9 Correct 479 ms 239900 KB Output is correct
10 Correct 415 ms 239900 KB Output is correct
11 Correct 523 ms 240300 KB Output is correct
12 Correct 571 ms 240548 KB Output is correct
13 Correct 476 ms 240552 KB Output is correct
14 Correct 483 ms 240684 KB Output is correct
15 Correct 551 ms 240684 KB Output is correct
16 Correct 573 ms 240684 KB Output is correct
17 Correct 576 ms 240684 KB Output is correct
18 Correct 603 ms 240684 KB Output is correct
19 Correct 495 ms 240684 KB Output is correct
20 Correct 483 ms 240684 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 237560 KB Output is correct
2 Correct 188 ms 237564 KB Output is correct
3 Correct 183 ms 237708 KB Output is correct
4 Correct 185 ms 237708 KB Output is correct
5 Correct 184 ms 237708 KB Output is correct
6 Correct 183 ms 237756 KB Output is correct
7 Correct 183 ms 237756 KB Output is correct
8 Correct 191 ms 237756 KB Output is correct
9 Correct 194 ms 237756 KB Output is correct
10 Correct 187 ms 237788 KB Output is correct
11 Correct 187 ms 237860 KB Output is correct
12 Correct 191 ms 237860 KB Output is correct
13 Correct 187 ms 237884 KB Output is correct
14 Correct 185 ms 237884 KB Output is correct
15 Correct 191 ms 237884 KB Output is correct
16 Correct 180 ms 237884 KB Output is correct
17 Correct 187 ms 237892 KB Output is correct
18 Correct 193 ms 237892 KB Output is correct
19 Correct 220 ms 237976 KB Output is correct
20 Correct 236 ms 238328 KB Output is correct
21 Correct 264 ms 238368 KB Output is correct
22 Correct 265 ms 238748 KB Output is correct
23 Correct 320 ms 239260 KB Output is correct
24 Correct 479 ms 239900 KB Output is correct
25 Correct 415 ms 239900 KB Output is correct
26 Correct 523 ms 240300 KB Output is correct
27 Correct 571 ms 240548 KB Output is correct
28 Correct 476 ms 240552 KB Output is correct
29 Correct 483 ms 240684 KB Output is correct
30 Correct 551 ms 240684 KB Output is correct
31 Correct 573 ms 240684 KB Output is correct
32 Correct 576 ms 240684 KB Output is correct
33 Correct 603 ms 240684 KB Output is correct
34 Correct 495 ms 240684 KB Output is correct
35 Correct 483 ms 240684 KB Output is correct
36 Correct 188 ms 240684 KB Output is correct
37 Correct 171 ms 240684 KB Output is correct
38 Correct 204 ms 240684 KB Output is correct
39 Correct 220 ms 240684 KB Output is correct
40 Correct 254 ms 240684 KB Output is correct
41 Correct 305 ms 240684 KB Output is correct
42 Correct 369 ms 240684 KB Output is correct
43 Correct 447 ms 240684 KB Output is correct
44 Correct 653 ms 240684 KB Output is correct
45 Correct 491 ms 240684 KB Output is correct
46 Correct 598 ms 240684 KB Output is correct
47 Correct 739 ms 240684 KB Output is correct
48 Correct 681 ms 240684 KB Output is correct
49 Correct 731 ms 240684 KB Output is correct
50 Correct 712 ms 240684 KB Output is correct
51 Correct 744 ms 240684 KB Output is correct
52 Correct 745 ms 240684 KB Output is correct
53 Correct 756 ms 240684 KB Output is correct
54 Correct 775 ms 240684 KB Output is correct
55 Correct 775 ms 240684 KB Output is correct