Submission #98084

#	Time	Username	Problem	Language	Result	Execution time	Memory
98084		dndhk	Worst Reporter 2 (JOI16_worst_reporter2)	C++14	100 / 100	589 ms	26356 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 chk[MAX_N+1];
int ans;

struct SEG{
	SEG(int l, int r, int lazy, int mn) : l(l), r(r), lazy(lazy), mn(mn) {}
	int l, r;
	int lazy, mn;
};
vector<SEG> seg;
vector<int> cnt;

void init(int idx, int s, int e){
	seg.push_back({-1, -1, 0, INF});
	if(s==e)	return;
	seg[idx].l = seg.size(); init(seg[idx].l, s, (s+e)/2);
	seg[idx].r = seg.size(); init(seg[idx].r, (s+e)/2+1, e);
}

void update(int idx, int s, int e, int x, int y){
	if(s!=e && seg[idx].lazy!=0){
		seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mn += seg[idx].lazy;
		seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mn += seg[idx].lazy;
		seg[idx].lazy = 0;
	}
	seg[idx].mn = min(seg[idx].mn, y);
	if(s==e)	return;
	if(x<=(s+e)/2)	update(seg[idx].l, s, (s+e)/2, x, y);
	else	update(seg[idx].r, (s+e)/2+1, e, x, y);
}

void lazy(int idx, int s, int e, int x, int y, int z){
	if(idx==-1)	return;
	if(s!=e && seg[idx].lazy!=0){
		seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mn += seg[idx].lazy;
		seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mn += seg[idx].lazy;
		seg[idx].lazy = 0;
	}
	if(x<=s && e<=y){
		seg[idx].lazy += z; seg[idx].mn += z; return;
	}
	else if(x>e || y<s)	return;
	lazy(seg[idx].l, s, (s+e)/2, x, y, z); lazy(seg[idx].r, (s+e)/2+1, e, x, y, z);
	seg[idx].mn = min(seg[seg[idx].l].mn, seg[seg[idx].r].mn);
}

int min(int idx, int s, int e, int x, int y){
	if(idx==-1)	return INF;
	if(s!=e && seg[idx].lazy!=0){
		seg[seg[idx].l].lazy += seg[idx].lazy; seg[seg[idx].l].mn += seg[idx].lazy;
		seg[seg[idx].r].lazy += seg[idx].lazy; seg[seg[idx].r].mn += seg[idx].lazy;
		seg[idx].lazy = 0;
	}
	if(x<=s && e<=y){
		return seg[idx].mn;
	}else if(x>e || y<s)	return INF;
	return min(min(seg[idx].l, s, (s+e)/2, x, y), min(seg[idx].r, (s+e)/2+1, e, x, y));
}


bool match(int x, int y){
	//cout<<'*'<<x<<' '<<y<<endl;
	if(cnt.empty())	return true;
	int s = 0, e = cnt.size(), m;
	while(s<e){
		m = (s+e)/2;
		if(cnt[m]>=y)	e = m;
		else	s = m+1;
	}
	lazy(0, 0, N-1, s, cnt.size()-1, -1);
	if(min(0, 0, N-1, 0, cnt.size()-1)>=0){
		return true;
	}
	lazy(0, 0, N-1, s, cnt.size()-1, 1);	return false;
}

int main(){
	scanf("%d", &N);	
	init(0, 0, N-1);
	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;
	int t = 0, num = 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++; num++;
		}   
		if(!g[v1[i].FI].empty() && match(i, g[v1[i].FI].back())){
			int k = g[v1[i].FI].back();
			//cout<<i<<' '<<k<<endl;
			//cout<<i<<' '<<k<<endl;
			ans--;
			g[v1[i].FI].pop_back(); num--;
		}else{
			update(0, 0, N-1, t, num-t-1);
			cnt.push_back(idx[i]);
			t++;
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:129:8: warning: unused variable 'k' [-Wunused-variable]
    int k = g[v1[i].FI].back();
        ^
worst_reporter2.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); 
  ~~~~~^~~~~~~~~~
worst_reporter2.cpp:109: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:112: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: 30 / 30
• Subtask 4: 40 / 40