Submission #1200692

#TimeUsernameProblemLanguageResultExecution timeMemory
12006928pete8허수아비 (JOI14_scarecrows)C++20
100 / 100
125 ms18384 KiB
#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 ("03,unroll-lopps") #define int long long using namespace std; const int mod=1e9+7,mxn=1e6+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 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:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
scarecrows.cpp:22:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   22 | void setIO(string name){
      |                       ^
scarecrows.cpp:30:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   30 | bool cmp2(pii a,pii b){
      |                      ^
scarecrows.cpp:33:21: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   33 | void dnc(int l,int r){
      |                     ^
scarecrows.cpp:65:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   65 | int32_t main(){
      |              ^
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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...