oj.uz

Submission #55356

# Submission time Handle Problem Language Result Execution time Memory
55356 2018-07-07T05:18:32 Z 김세빈(#1545) Employment (JOI16_employment) C++11
0 / 100
 14 ms 12388 KB 
#include <bits/stdc++.h>

using namespace std;

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

node T[1010101];
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=1;i<=n;i++){
		printf("%d ", K[i]);
	}
	printf("\n");
	
	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:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~
employment.cpp:73:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
employment.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &k);
    ~~~~~^~~~~~~~~~
employment.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", A+k);
    ~~~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 12388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 12156 KB Output isn't correct
2 Halted 0 ms 0 KB -