Submission #257522

#	Time	Username	Problem	Language	Result	Execution time	Memory
257522		songc	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	381 ms	26744 KiB

worst_reporter2

#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M, ans;
int T[1606060], lz[1606060];
pii A[404040];
vector<int> S[202020];

void busy(int id){
	T[id*2] += lz[id], T[id*2+1] += lz[id];
	lz[id*2] += lz[id], lz[id*2+1] += lz[id];
	lz[id] = 0;
}

void upd(int id, int s, int e, int ts, int te, int v){
	if (e < ts || te < s) return;
	if (ts <= s && e <= te){T[id] += v, lz[id] += v; return;}
	busy(id);
	int m = s+e>>1;
	upd(id*2, s, m, ts, te, v);
	upd(id*2+1, m+1, e, ts, te, v);
	T[id] = min(T[id*2], T[id*2+1]);
}

int main(){
	scanf("%d", &N);
	for (int i=1; i<=N; i++){
		scanf("%d %d", &A[i].se, &A[i].fi);
		A[i].fi = A[i].fi*2;
	}
	for (int i=N+1; i<=2*N; i++){
		scanf("%d %d", &A[i].se, &A[i].fi);
		A[i].fi = A[i].fi*2+1;
	}
	sort(A+1, A+2*N+1);
	for (int i=1; i<=2*N; i++) upd(1, 1, 2*N, i, 2*N, (A[i].fi&1)?-1:1);
	for (int i=1; i<=2*N; i++){
		if (A[i].fi & 1){
			if (S[A[i].se].size()){
				upd(1, 1, 2*N, S[A[i].se].back(), i-1, -1);
				if (T[1] >= 0) S[A[i].se].pop_back();
				else upd(1, 1, 2*N, S[A[i].se].back(), i-1, 1), ans++;
			}
			else ans++;
		}
		else S[A[i].se].pb(i);
	} 
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'void upd(int, int, int, int, int, int)':
worst_reporter2.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e>>1;
          ~^~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i].se, &A[i].fi);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i].se, &A[i].fi);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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