Submission #1200695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200695		8pete8	허수아비 (JOI14_scarecrows)	C++20	15 / 100	68 ms	8976 KiB

scarecrows

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native,sse,sse2,sse3")
using namespace std;
const int mod=1e9+7,mxn=2e5+5,inf=3e18,minf=-3e18,lg=31,Mxn=6e6,base=131;
//#undef int
int n,k,m,q,L,T;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
vector<pii>point;
int mx[mxn+10];
int ans=0;
bool cmp2(pii a,pii b){
	return a.s<b.s;
}
void inline dnc(int l,int r){
	if(l==r)return;
	int mid=l+(r-l)/2;
	dnc(l,mid);
	dnc(mid+1,r);
	vector<pii>have;
	//x decreasing
	//y increasing
	vector<pair<pii,int>>ord;
	int c1=l,c2=mid+1;
	int cnt=0;
	while(c2<=r){
		while(c1<=mid&&point[c1].s<point[c2].s){
			while(have.size()&&have.back().f<point[c1].f){
				have.pop_back();
			}
			have.pb(point[c1]);
			ord.pb({point[c1],mx[c1]});
			c1++;
		}
		auto it=lb(all(have),make_pair(0,mx[c2]),cmp2)-have.begin();
		ans+=have.size()-it;
		if(have.size())mx[c2]=max(mx[c2],have.back().s);
		ord.pb({point[c2],mx[c2]});
		c2++;
	}
	while(c1<=mid)ord.pb({point[c1],mx[c1]}),c1++;
	for(int i=0;i<ord.size();i++){
		point[l+i]=ord[i].f;
		mx[l+i]=ord[i].s;
	}
}
int32_t main(){
	fastio
	cin>>n;
	for(int i=0;i<n;i++){
		int a,b;cin>>a>>b;
		point.pb({a,b});
	}
	sort(all(point));
	dnc(0,n-1);
	cout<<ans;
}

/*

*/

Compilation message (stderr)

scarecrows.cpp:19:35: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
   19 | const int mod=1e9+7,mxn=2e5+5,inf=3e18,minf=-3e18,lg=31,Mxn=6e6,base=131;
      |                                   ^~~~
scarecrows.cpp:19:45: warning: overflow in conversion from 'double' to 'int' changes value from '-3.0e+18' to '-2147483648' [-Woverflow]
   19 | const int mod=1e9+7,mxn=2e5+5,inf=3e18,minf=-3e18,lg=31,Mxn=6e6,base=131;
      |                                             ^~~~~
scarecrows.cpp: In function 'void setIO(std::string)':
scarecrows.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
scarecrows.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 85