oj.uz

Submission #189405

# Submission time Handle Problem Language Result Execution time Memory
189405 2020-01-14T03:08:39 Z dndhk Employment (JOI16_employment) C++14
100 / 100
 1322 ms 41244 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;

int N, M, K;
int A[MAX_N+1];
vector<int> vt;
struct S{
	int t, a, b;
};
vector<S> query;
map<int, int> mp;

void input(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++){
		scanf("%d", &A[i]);
		vt.pb(A[i]);
	}
	for(int i=1; i<=M; i++){
		int t, a, b=0;
		scanf("%d", &t);
		if(t==1){
			scanf("%d", &a);
			vt.pb(a);
		}else{
			scanf("%d%d", &a, &b);
			vt.pb(b);
		}
		query.pb({t, a, b});
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for(int i=0; i<vt.size(); i++){
		mp[vt[i]] = i+1;
	}
	for(int i=1; i<=N; i++)	A[i] = mp[A[i]];
	for(int i=0; i<query.size(); i++){
		if(query[i].t==1){
			query[i].a = mp[query[i].a];
		}else{
			query[i].b = mp[query[i].b];
		}
	}
	K = vt.size();}

struct SEG{
	struct NODE{
		int l, r;
		int sum;
	};
	int SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, 0});
	}
	void Init(int x){
		SZ = x;
		add();
		init(0, 1, SZ);
	}
	void init(int idx, int s, int e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l, s, (s+e)/2);
		init(seg[idx].r, (s+e)/2+1, e);
	}
	void Add(int x, int y, int z){
		add(0, 1, SZ, x, y, z);
	}
	void add(int idx, int s, int e, int x, int y, int z){
		if(x<=s && e<=y){
			seg[idx].sum+=z;
			return;
		}
		if(x>e || y<s)	return;
		add(seg[idx].l, s, (s+e)/2, x, y, z);
		add(seg[idx].r, (s+e)/2+1, e, x, y, z);
	}
	int Sum(int x){
		return sum(0, 1, SZ, x);
	}
	int sum(int idx, int s, int e, int k){
		if(s==e)	return seg[idx].sum;
		if(k<=(s+e)/2){
			return seg[idx].sum+sum(seg[idx].l, s, (s+e)/2, k);
		}else{
			return seg[idx].sum+sum(seg[idx].r, (s+e)/2+1, e, k);
		}
	}
}Seg;



void add(int x, int y){
	if(N==1){
		Seg.Add(1, y, 1);
		return;
	}
	if(x==1){
		if((pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}
	}else if(x==N){
		if((pii){y, x} > (pii){A[x-1], x-1}){
			Seg.Add(1, y, 1);
		}
	}else{
		if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}
	}
}

void rmv(int x, int y){
	if(N==1){
		Seg.Add(1, y, -1);
		return;
	}
	if(x==1){
		if((pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}
	}else if(x==N){
		if((pii){y, x} > (pii){A[x-1], x-1}){
			Seg.Add(1, y, -1);
		}
	}else{
		if((pii){y, x} > (pii){A[x-1], x-1} && (pii){y, x} > (pii){A[x+1], x+1}){
			Seg.Add(1, y, -1);
		}else if((pii){y, x} < (pii){A[x-1], x-1} && (pii){y, x} < (pii){A[x+1], x+1}){
			Seg.Add(1, y, 1);
		}
	}
}

int main(){
	input();
	Seg.Init(K);
	for(int i=1; i<=N; i++){
		add(i, A[i]);
	}
	for(int i=0; i<query.size(); i++){
		int t = query[i].t, a = query[i].a, b = query[i].b;
		if(t==2){
			rmv(a, A[a]);
			if(a!=1){
				rmv(a-1, A[a-1]);
			}if(a!=N){
				rmv(a+1, A[a+1]);
			}
			A[a] = b;
			add(a, b);
			if(a!=1){
				add(a-1, A[a-1]);
			}if(a!=N){
				add(a+1, A[a+1]);
			}
		}else{
			printf("%d\n", Seg.Sum(a));
		}
	}
	return 0;
}

Compilation message

employment.cpp: In function 'void input()':
employment.cpp:41:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
employment.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'int main()':
employment.cpp:153:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<query.size(); i++){
               ~^~~~~~~~~~~~~
employment.cpp: In function 'void input()':
employment.cpp:22: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:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &A[i]);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
employment.cpp:31:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
employment.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 712 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 6 ms 760 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 6 ms 760 KB Output is correct
15 Correct 6 ms 764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 6 ms 952 KB Output is correct
4 Correct 39 ms 3460 KB Output is correct
5 Correct 88 ms 6580 KB Output is correct
6 Correct 187 ms 10476 KB Output is correct
7 Correct 244 ms 17104 KB Output is correct
8 Correct 325 ms 19532 KB Output is correct
9 Correct 607 ms 34304 KB Output is correct
10 Correct 553 ms 34000 KB Output is correct
11 Correct 738 ms 37428 KB Output is correct
12 Correct 811 ms 40316 KB Output is correct
13 Correct 923 ms 40156 KB Output is correct
14 Correct 1187 ms 39692 KB Output is correct
15 Correct 817 ms 39704 KB Output is correct
16 Correct 957 ms 40612 KB Output is correct
17 Correct 1136 ms 40496 KB Output is correct
18 Correct 1043 ms 40632 KB Output is correct
19 Correct 988 ms 40616 KB Output is correct
20 Correct 828 ms 40648 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 5 ms 712 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 5 ms 760 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 6 ms 760 KB Output is correct
12 Correct 6 ms 760 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 6 ms 760 KB Output is correct
15 Correct 6 ms 764 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 4 ms 760 KB Output is correct
18 Correct 6 ms 952 KB Output is correct
19 Correct 39 ms 3460 KB Output is correct
20 Correct 88 ms 6580 KB Output is correct
21 Correct 187 ms 10476 KB Output is correct
22 Correct 244 ms 17104 KB Output is correct
23 Correct 325 ms 19532 KB Output is correct
24 Correct 607 ms 34304 KB Output is correct
25 Correct 553 ms 34000 KB Output is correct
26 Correct 738 ms 37428 KB Output is correct
27 Correct 811 ms 40316 KB Output is correct
28 Correct 923 ms 40156 KB Output is correct
29 Correct 1187 ms 39692 KB Output is correct
30 Correct 817 ms 39704 KB Output is correct
31 Correct 957 ms 40612 KB Output is correct
32 Correct 1136 ms 40496 KB Output is correct
33 Correct 1043 ms 40632 KB Output is correct
34 Correct 988 ms 40616 KB Output is correct
35 Correct 828 ms 40648 KB Output is correct
36 Correct 4 ms 504 KB Output is correct
37 Correct 7 ms 760 KB Output is correct
38 Correct 8 ms 1016 KB Output is correct
39 Correct 80 ms 3636 KB Output is correct
40 Correct 110 ms 5996 KB Output is correct
41 Correct 184 ms 10416 KB Output is correct
42 Correct 386 ms 16532 KB Output is correct
43 Correct 500 ms 19672 KB Output is correct
44 Correct 810 ms 36304 KB Output is correct
45 Correct 610 ms 33436 KB Output is correct
46 Correct 678 ms 34168 KB Output is correct
47 Correct 947 ms 40544 KB Output is correct
48 Correct 985 ms 40824 KB Output is correct
49 Correct 1270 ms 40788 KB Output is correct
50 Correct 950 ms 40452 KB Output is correct
51 Correct 998 ms 41192 KB Output is correct
52 Correct 1322 ms 41188 KB Output is correct
53 Correct 997 ms 41212 KB Output is correct
54 Correct 1141 ms 41148 KB Output is correct
55 Correct 1043 ms 41244 KB Output is correct