Submission #1012739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012739		pcc	Worst Reporter 2 (JOI16_worst_reporter2)	C++17	100 / 100	227 ms	40396 KiB

worst_reporter2

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

#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()

const int mxn = 4e5+10;
pii arr[mxn],brr[mxn];
vector<pii> v;
int N;
vector<int> stk[mxn];

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	SEG(){}
	pii seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = min(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
		return;
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now].fs+seg[now].sc;
		if(mid>=e)return getval(ls,l,mid,s,e)+seg[now].sc;
		else if(mid<s)return getval(rs,mid+1,r,s,e)+seg[now].sc;
		else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e))+seg[now].sc;
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int pref[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 0;i<N;i++)cin>>arr[i].fs>>arr[i].sc,v.push_back(pii(arr[i].sc,-arr[i].fs));
	for(int i = 0;i<N;i++)cin>>brr[i].fs>>brr[i].sc,v.push_back(pii(brr[i].sc,brr[i].fs));
	sort(_all(v));
	for(int i = 0;i<v.size();i++){
		if(i)pref[i] = pref[i-1];
		if(v[i].sc<0)pref[i]++;
		else pref[i]--;
		seg.modify(0,0,mxn,i,i,pref[i]);
	}
	int ans = N;
	for(int i = 0;i<v.size();i++){
		if(v[i].sc<0){
			v[i].sc = -v[i].sc;
			stk[v[i].sc].push_back(i);
		}
		else{
			int tar = v[i].sc;
			if(stk[tar].empty())continue;
			int pos = stk[tar].back();
			if(seg.getval(0,0,mxn,pos,i-1) == 0)continue;
			ans--;
			seg.modify(0,0,mxn,pos,pos,mxn);
			seg.modify(0,0,mxn,i,i,mxn);
			seg.modify(0,0,mxn,pos,i,-1);
			stk[tar].pop_back();
		}
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:51:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
worst_reporter2.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~

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