Submission #261220

#	Time	Username	Problem	Language	Result	Execution time	Memory
261220		kdh9949	Employment (JOI16_employment)	C++17	100 / 100	353 ms	17660 KiB

employment

#include <bits/stdc++.h>
using namespace std;

struct Point{
	int x, p;
	bool operator<(const Point &oth) const {
		return x < oth.x;
	}
} ia[200010];

struct Query{
	int t, x, y;
} qa[200010];

const int sz = 524288;
struct Seg{
	int dat[1048576];
	int upd(int s, int e, int v){
		for(s += sz - 1, e += sz - 1; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) dat[s++] += v;
			if(e % 2 == 0) dat[e--] += v;
		}
	}
	int get(int x){
		int ret = 0;
		for(x += sz - 1; x; x /= 2) ret += dat[x];
		return ret;
	}
} S;

int n, q;
int xx[400010], xc;
int a[200010], s[400010], chk[200010];

void upd(int lx, int rx, int x, int v){
  if(rx < x){
		S.upd(1, x - 1, v);
  }
  else{
		S.upd(1, rx - 1, v);
		if(x < lx) S.upd(x, lx - 1, v);
  }
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i++){
		scanf("%d", a + i);
		xx[xc++] = a[i];
	}
	for(int i = 0; i < q; i++){
		int t, x, y; scanf("%d%d", &t, &x);
		if(t == 2) scanf("%d", &y);
		qa[i] = {t, x, y};
		xx[xc++] = (t == 1 ? x : y);
	}
	sort(xx, xx + xc);
	for(int i = 1; i <= n; i++) a[i] = (int)(lower_bound(xx, xx + xc, a[i]) - xx + 1);
	for(int i = 0; i < q; i++){
		if(qa[i].t == 1) qa[i].x = (int)(lower_bound(xx, xx + xc, qa[i].x) - xx + 1);
		else qa[i].y = (int)(lower_bound(xx, xx + xc, qa[i].y) - xx + 1);
	}
	for(int i = 1; i <= n; i++) ia[i] = {a[i], i};
	sort(ia + 1, ia + n + 1);
	s[0] = 1;
	int lst = 0, cur = 1;
	a[0] = a[n + 1] = -1;
	chk[0] = chk[n + 1] = 1;
	for(int i = 1; i <= n; ){
		int j; for(j = i + 1; j <= n && ia[j].x == ia[i].x; j++);
		for(; lst < ia[i].x ; lst++) s[lst] = cur;
		for(int k = i; k < j; k++){
			chk[ia[k].p] = 1;
			cur -= (chk[ia[k].p - 1] + chk[ia[k].p + 1] - 1);
		}
		i = j;
	}
	for(; lst <= xc; lst++) s[lst] = cur;
	for(int i = 0; i < q; i++){
		if(qa[i].t == 1){
			printf("%d\n", s[qa[i].x - 1] + S.get(qa[i].x - 1));
		}
		else{
			int lx = a[qa[i].x - 1], rx = a[qa[i].x + 1];
			if(lx > rx) swap(lx, rx);
			int px = a[qa[i].x], cx = qa[i].y;
			upd(lx, rx, px, -1);
			upd(lx, rx, cx, 1);
			a[qa[i].x] = cx;
		}
	}
}

Compilation message (stderr)

employment.cpp: In member function 'int Seg::upd(int, int, int)':
employment.cpp:23:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^
employment.cpp: In function 'int main()':
employment.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~
employment.cpp:52:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int t, x, y; scanf("%d%d", &t, &x);
                ~~~~~^~~~~~~~~~~~~~~~
employment.cpp:53:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(t == 2) scanf("%d", &y);
              ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60