Submission #258560

#	Time	Username	Problem	Language	Result	Execution time	Memory
258560		arnold518	Employment (JOI16_employment)	C++14	100 / 100	751 ms	20212 KiB

employment

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 8e5;

int N, M, S, A[MAXN+10];

struct Query
{
	int t, a, b;
};
Query B[MAXN+10];

vector<int> comp;
int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; }

int tree[MAXN*4+10];
void update(int node, int tl, int tr, int l, int r, int k)
{
	if(l>r) return;
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r) { tree[node]+=k; return; }
	int mid=tl+tr>>1;
	update(node*2, tl, mid, l, r, k);
	update(node*2+1, mid+1, tr, l, r, k);
}
int query(int node, int tl, int tr, int p)
{
	if(tl==tr) return tree[node];
	int mid=tl+tr>>1;
	if(p<=mid) return query(node*2, tl, mid, p)+tree[node];
	else return query(node*2+1, mid+1, tr, p)+tree[node];
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);

	for(i=1; i<=M; i++)
	{
		int t=0, a=0, b=0;
		scanf("%d", &t);
		if(t==1) scanf("%d", &a), comp.push_back(a);
		else scanf("%d%d", &a, &b), comp.push_back(b), comp.push_back(b+1);
		B[i].t=t; B[i].a=a; B[i].b=b;
	}

	comp.push_back(0);
	comp.push_back(1);
	for(i=1; i<=N; i++)
	{
		comp.push_back(A[i]);
		comp.push_back(A[i]+1);
	}
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end());
	S=comp.size();

	for(i=1; i<=N+1; i++)
	{
		int a=getcomp(min(A[i-1], A[i])+1), b=getcomp(max(A[i-1], A[i]));
		update(1, 1, S, a, b, 1);
	}

	for(i=1; i<=M; i++)
	{
		int t=B[i].t, a=B[i].a, b=B[i].b;
		if(t==1) printf("%d\n", query(1, 1, S, getcomp(a))/2);
		else
		{
			int p, q;
			p=getcomp(min(A[a-1], A[a])+1), q=getcomp(max(A[a-1], A[a]));
			update(1, 1, S, p, q, -1);
			p=getcomp(min(A[a+1], A[a])+1), q=getcomp(max(A[a+1], A[a]));
			update(1, 1, S, p, q, -1);
			A[a]=b;
			p=getcomp(min(A[a-1], A[a])+1), q=getcomp(max(A[a-1], A[a]));
			update(1, 1, S, p, q, 1);
			p=getcomp(min(A[a+1], A[a])+1), q=getcomp(max(A[a+1], A[a]));
			update(1, 1, S, p, q, 1);
		}
	}
}

Compilation message (stderr)

employment.cpp: In function 'void update(int, int, int, int, int, int)':
employment.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int query(int, int, int, int)':
employment.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=tl+tr>>1;
          ~~^~~
employment.cpp: In function 'int main()':
employment.cpp:41:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
employment.cpp:43: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:44:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~
employment.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
employment.cpp:50:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(t==1) scanf("%d", &a), comp.push_back(a);
            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
employment.cpp:51:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   else scanf("%d%d", &a, &b), comp.push_back(b), comp.push_back(b+1);
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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