Submission #329874

#	Time	Username	Problem	Language	Result	Execution time	Memory
329874		arnold518	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	364 ms	33516 KiB

worst_reporter2

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

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

const int MAXN = 4e5;

int N;
pii _A[MAXN+10];
int A[MAXN+10];

int B[MAXN+10];
vector<int> V[MAXN+10];

struct SEG
{
	int tree[MAXN*4+10], lazy[MAXN*4+10];

	void init(int node, int tl, int tr)
	{
		lazy[node]=0;
		if(tl==tr)
		{
			tree[node]=B[tl];
			return;
		}
		int mid=tl+tr>>1;
		init(node*2, tl, mid);
		init(node*2+1, mid+1, tr);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}

	void busy(int node, int tl, int tr)
	{
		tree[node]+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}

	void update(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			lazy[node]--;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r);
		update(node*2+1, mid+1, tr, l, r);
		tree[node]=min(tree[node*2], tree[node*2+1]);
	}

	int query(int node, int tl, int tr, int l, int r)
	{
		busy(node, tl, tr);
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return 987654321;
		int mid=tl+tr>>1;
		return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
	}
}seg;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &_A[i].second, &_A[i].first), _A[i].second*=-1;
	for(int i=1; i<=N; i++) scanf("%d%d", &_A[i+N].second, &_A[i+N].first);

	N*=2;
	sort(_A+1, _A+N+1);
	for(int i=1; i<=N; i++) A[i]=_A[i].second;
	for(int i=1; i<=N; i++)
	{
		if(A[i]<0) B[i]=B[i-1]+1;
		else B[i]=B[i-1]-1;
	}
	seg.init(1, 1, N);

	int ans=N/2;
	for(int i=1; i<=N; i++)
	{	
		if(A[i]<0)
		{
			V[-A[i]].push_back(i);
		}
		else
		{
			if(V[A[i]].empty()) continue;

			if(seg.query(1, 1, N, V[A[i]].back(), i-1)<1)
			{
				V[A[i]].clear();
			}
			else
			{
				seg.update(1, 1,  N, V[A[i]].back(), i-1);
				V[A[i]].pop_back();
				ans--;
			}
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

worst_reporter2.cpp: In member function 'void SEG::init(int, int, int)':
worst_reporter2.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid=tl+tr>>1;
      |           ~~^~~
worst_reporter2.cpp: In member function 'void SEG::update(int, int, int, int, int)':
worst_reporter2.cpp:56:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |   int mid=tl+tr>>1;
      |           ~~^~~
worst_reporter2.cpp: In member function 'int SEG::query(int, int, int, int, int)':
worst_reporter2.cpp:67:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |   int mid=tl+tr>>1;
      |           ~~^~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:75:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |  for(int i=1; i<=N; i++) scanf("%d%d", &_A[i].second, &_A[i].first), _A[i].second*=-1;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:76:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |  for(int i=1; i<=N; i++) scanf("%d%d", &_A[i+N].second, &_A[i+N].first);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40