Submission #955426

#TimeUsernameProblemLanguageResultExecution timeMemory
955426vjudge1IOI Fever (JOI21_fever)C++17
25 / 100
5031 ms79188 KiB
#include <bits/stdc++.h> #pragma optimize("Ofast") #pragma target("avx2") using namespace std; #define ll long long #define ld long double #define pb push_back #define pf push_front #define pii pair<int,int> #define all(v) v.begin(),v.end() #define F first #define S second #define mem(a,i) memset(a,i,sizeof(a)) #define sz(s) (int)s.size() #define y1 yy #define ppb pop_back #define lb lower_bound #define ub upper_bound #define gcd(a,b) __gcd(a,b) #define in insert #define int ll const int MAX=1e6+15; const int B=300; const int N=104; const int block=400; const int maxB=MAX/B+10; const ll inf=1e18; const int mod=998244353; const int mod1=1e9+9; const ld eps=1e-9; // int dx[8]={1,0,-1,0,1,-1,-1,1}; // int dy[8]={0,1,0,-1,1,-1,1,-1}; int binpow(int a,int n){ if(!n)return 1; if(n%2==1)return a*binpow(a,n-1)%mod; int k=binpow(a,n/2); return k*k%mod; } int n; pii a[MAX]; int b[MAX]; int d[MAX]; int dx[MAX],dy[MAX]; vector<int> vx[MAX],vy[MAX]; int ans; void calc(int start,int nap){ b[start]=nap; set<pii> st; for(int i=1;i<=n;i++)d[i]=inf; d[start]=0; st.in({0,start}); while(!st.empty()){ int v=st.begin()->S; st.erase(st.begin()); for(auto to:vx[dx[v]]){ if(d[to]>abs(a[v].F-a[to].F)&&d[v]<=abs(a[v].F-a[to].F)){ if(b[v]==1){ if(a[to].F<a[v].F){ b[to]=2; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==2){ if(a[to].F>a[v].F){ b[to]=1; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==3){ if(a[to].F>a[v].F){ b[to]=4; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==4){ if(a[to].F<a[v].F){ b[to]=3; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } } } for(auto to:vy[dy[v]]){ if(d[to]>abs(a[v].F-a[to].F)&&d[v]<=abs(a[v].F-a[to].F)){ if(b[v]==1){ if(a[to].F>a[v].F){ b[to]=4; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==2){ if(a[to].F>a[v].F){ b[to]=3; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==3){ if(a[to].F<a[v].F){ b[to]=2; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } if(b[v]==4){ if(a[to].F<a[v].F){ b[to]=1; st.erase({d[to],to}); d[to]=abs(a[v].F-a[to].F); st.in({d[to],to}); } } } } } int cur=0; for(int i=1;i<=n;i++){ cur+=(d[i]!=inf); // cout<<d[i]<<" "<<b[i]<<"\n"; } ans=max(ans,cur); } void solve(){ cin>>n; set<int> d; map<int,int> mp; int cur=0; for(int i=1;i<=n;i++){ cin>>a[i].F>>a[i].S; d.in(a[i].F+a[i].S); } for(int x:d)mp[x]=++cur; for(int i=1;i<=n;i++){ dx[i]=mp[a[i].F+a[i].S]; vx[mp[a[i].F+a[i].S]].pb(i); } cur=0; mp.clear(); d.clear(); for(int i=1;i<=n;i++){ d.in(a[i].F-a[i].S); } for(int x:d)mp[x]=++cur; for(int i=1;i<=n;i++){ dy[i]=mp[a[i].F-a[i].S]; vy[mp[a[i].F-a[i].S]].pb(i); } for(int i=1;i<=4;i++){ calc(1,i); } cout<<ans; } signed main(){ // freopen("help.in","r",stdin); // freopen("help.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // prec(); int t=1; // cin>>t; while(t--)solve(); }

Compilation message (stderr)

fever.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
fever.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...