Submission #593020

#TimeUsernameProblemLanguageResultExecution timeMemory
593020Andyvanh1Zoltan (COCI16_zoltan)C++14
140 / 140
74 ms27084 KiB
#include <iostream> #include <vector> #include <math.h> #include <algorithm> #include <map> #include <set> #include <iomanip> #include <queue> #include <stack> using namespace std; #define vt vector #define pb push_back #define all(x) (x).begin(),(x).end() #define FORR1(x) for(int i = 0; i < (x); i++) #define FORR2(i,x) for (int (i) = 0; (i) < (x); (i)++) #define MOD 1000000007 typedef long long ll; typedef pair<int,int> pii; typedef pair<int,ll> pil; typedef long double ld; typedef vt<int> vi; typedef pair<int,pair<int,int>> piii; struct fwtree{ vi arr; int sz; void init(int n){ arr.resize(n+1); sz = n; FORR1(n+1)arr[i] = 0; } //remember difference between 0- and 1- indexing void add(int index, int val){ while(index <= sz){ arr[index]+=val; index+=index&-index; } } ll get(int index){ ll val = 0; while(index!=0){ val+=arr[index]; index-=index&-index; } return val; } ll get(int l, int r){ return get(r)-get(l-1); } }; int N, O, M; vi ceo; ll fastexp(ll n, int m){ if(m==0)return 1; ll cur = fastexp(n,m/2); cur = cur*cur; cur%=MOD; if(m&1){ cur*=n; cur%=MOD; } return cur; } ll inv(ll x){ return fastexp(x,MOD-2); } vt<vi> adjlist; int degree[200005]; int dp[200005]; int ans = 0; void dfs_dp(int node, int par){ int cur = 0; for(auto& e: adjlist[node]){ if(e!=par){ dfs_dp(e,node); cur = max(cur,dp[e]); } } dp[node] = max(cur,degree[node]); } void dfs_ans(int node, int par){ int k = 0; for(auto& e: adjlist[node]){ if(e!=par){ dfs_ans(e,node); if(dp[e]<=2)k++; } } if(k>1)ans+=k-1; } ll fac[500005]; ll invfac[500005]; bool arr[102][102][102]; vt<vi> adj; int clr[102]; bool visited[102]; bool chk = true; void dfs(int node){ visited[node] = true; for(auto& e: adj[node]){ if(visited[e]){ if((clr[e]^1)!=clr[node]){ chk = false; }else{ clr[e] = clr[node]^1; dfs(e); } } } } vt<vi> tr; void solve(){ int n; cin>>n; vi arr(n); FORR1(n)cin>>arr[i]; vi up(n); vi dn(n); vi upct(n); vi dnct(n); vi curup(n+1); vi curdn(n+1); vi indup(n+1); vi inddn(n+1); int at1 = 1; int at2 = 1; FORR1(n+1){ curup[i] = -1; curdn[i] = -1; indup[i] = -1; inddn[i] = -1; } vt<vt<pii>> adjup(n+1); vt<vt<pii>> adjdn(n+1); vi relup(n+1); vi reldn(n+1); vi sumup(n+1); vi sumdn(n+1); FORR1(n+1){ sumup[i] = sumdn[i] = relup[i] = reldn[i] = 0; } for(int i = n-1; i >=0; i--){ if(i==n-1){ curdn[1] = arr[i]; inddn[1] = i; dn[i] = 1; dnct[i] = 1; sumdn[1] = 1; adjdn[1].pb({arr[i],1}); }else{ if(arr[i]>curdn[at1]){ at1++; curdn[at1] = arr[i]; inddn[at1] = i; while(arr[i]<=adjdn[at1-1][reldn[at1-1]].first){ sumdn[at1-1]-=adjdn[at1-1][reldn[at1-1]].second; if(sumdn[at1-1]<0)sumdn[at1-1]+=MOD; reldn[at1-1]++; } dn[i] = at1; dnct[i] = sumdn[at1-1]; adjdn[at1].pb({arr[i],dnct[i]}); sumdn[at1]+=dnct[i]; }else{ int l = 1; int r = at1; while(l!=r){ int mid = (l+r)>>1; if(curdn[mid]<arr[i]){ l = mid+1; }else{ r = mid; } } curdn[l] = arr[i]; inddn[l] = i; dn[i] = l; if(l==1){ dnct[i] = 1; }else{ while(arr[i]<=adjdn[l-1][reldn[l-1]].first){ sumdn[l-1]-=adjdn[l-1][reldn[l-1]].second; if(sumdn[l-1]<0)sumdn[l-1]+=MOD; reldn[l-1]++; } dnct[i] = sumdn[l-1]; } adjdn[l].pb({arr[i],dnct[i]}); sumdn[l]+=dnct[i]; if(sumdn[l]>=MOD)sumdn[l]-=MOD; } } } for(int i = n-1; i >=0; i--){ if(i==n-1){ curup[1] = arr[i]; indup[1] = i; up[i] = 1; upct[i] = 1; sumup[1] = 1; adjup[1].pb({arr[i],1}); }else{ if(arr[i]<curup[at2]){ at2++; curup[at2] = arr[i]; indup[at2] = i; while(arr[i]>=adjup[at2-1][relup[at2-1]].first){ sumup[at2-1]-=adjup[at2-1][relup[at2-1]].second; if(sumup[at2-1]<0)sumup[at2-1]+=MOD; relup[at2-1]++; } up[i] = at2; upct[i] = sumup[at2-1]; adjup[at2].pb({arr[i],upct[i]}); sumup[at2]+=upct[i]; }else{ int l = 1; int r = at2; while(l!=r){ int mid = (l+r)>>1; if(curup[mid]>arr[i]){ l = mid+1; }else{ r = mid; } } curup[l] = arr[i]; indup[l] = i; up[i] = l; if(l==1){ upct[i] = 1; }else{ while(arr[i]>=adjup[l-1][relup[l-1]].first){ sumup[l-1]-=adjup[l-1][relup[l-1]].second; if(sumup[l-1]<0)sumup[l-1]+=MOD; relup[l-1]++; } upct[i] = sumup[l-1]; } adjup[l].pb({arr[i],upct[i]}); sumup[l]+=upct[i]; if(sumup[l]>=MOD)sumup[l]-=MOD; } } } /*FORR1(n){ cout<<dn[i]<<" "<<dnct[i]<<'\n'; } cout<<"----\n"; FORR1(n){ cout<<up[i]<<" "<<upct[i]<<'\n'; }*/ int Max = 0; FORR1(n){ Max = max(Max, up[i]+dn[i]-1); } int val = 1; for(int i = 0; i < n-Max; i++){ val*=2; val%=MOD; } ll ans = 0; FORR1(n){ if(up[i]+dn[i]-1==Max){ ans+=(ll)upct[i]*dnct[i]; ans%=MOD; } } cout<<Max<<" "<<ans*val%MOD<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin>>t; while(t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...