Submission #98075

#	Time	Username	Problem	Language	Result	Execution time	Memory
98075		dndhk	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	30 / 100	2008 ms	5768 KiB

worst_reporter2

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200000;
int N;
vector<pii> v1, v2;
int idx[MAX_N+1];
vector<int> g[MAX_N+1];
int cnt[MAX_N+1];
int chk[MAX_N+1];
int ans;

bool match(int x, int y){
	int t = 0;
	for(int i = 0; i<x; i++){
		if(chk[i])	continue;
		t++;
		if(idx[i]>=y){
			int sum = 0;
			for(int j=0; j<=idx[i]; j++){
				sum+=cnt[j];
			}
			if(sum<=t)	return false;
		}
	}return true;
}

int main(){
	scanf("%d", &N);	for(int i=0; i<N; i++)	cnt[i]++;
	ans = N;
	for(int i=0 ;i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		v1.push_back({a, b});
	}for(int i=0; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		v2.push_back({a, b});
	}
	for(int i=0; i<N; i++){
		if(i==0)	idx[i] = 0;
		else	idx[i] = idx[i-1];
		while(idx[i]!=N-1 && v2[idx[i]+1].SE >= v1[i].SE){
			idx[i]++;
		}
	}
	int index = 0;
	for(int i=0; i<N; i++){
		while(index<N && v2[index].SE >= v1[i].SE){
			g[v2[index].FI].push_back(index); index++;
		}   
		if(!g[v1[i].FI].empty()){
			int k = g[v1[i].FI].back();
			//cout<<i<<' '<<k<<endl;
			if(match(i, k)){
				//cout<<i<<' '<<k<<endl;
				cnt[k]--; chk[i] = true; ans--;
				g[v1[i].FI].pop_back();
			}
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); for(int i=0; i<N; i++) cnt[i]++;
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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