fork download
copy 
  1. #include<iostream>
  2. #include<string>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<climits>
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define mp make_pair
  9. #define pb push_back
  10. #define ll long long
  11. #define VI vector<int>
  12. #define PII pair<int,int>
  13. #define VII vector<PII >
  14. #define ft first
  15. #define sd second
  16. #define rz(v,n) v.resize(n)
  17. #define VL vector<ll>
  18. #define VLL vector<pair<ll,ll> >
  19. #define PLL pair< ll,ll >
  20. #define all(v) v.begin(),v.end()
  21. #define IT iterator
  22. // Input/Output
  23. #define print(v) printf("%d\n",v)
  24. #define printll(v) printf("%lld\n",v)
  25. #define scan(v) scanf("%d",&v)
  26. #define scanll(v) scanf("%lld",&v)
  27. // loops
  28. #define FOR(i,a,b) for(int i=a;i<b;i++)
  29. #define rep(i,n) for(int i=0;i<n;i++)
  30. //extra
  31. #define ms(v,val) memset(v,val,sizeof(v))
  32. #define fill(v,val) fill(all(v),val)
  33. #define f_in(st) freopen(st,"r",stdin)
  34. #define f_out(st) freopen(st,"w",stdout)
  35. #define PIE 3.14159265358979323846264338327950
  36. #define MOD 1000000007
  37. #ifdef ONLINE_JUDGE
  38.  inline void inp( int &n )
  39.  {
  40.     n=0;
  41.     int ch=getchar_unlocked();int sign=1;
  42.     while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}
  43.  
  44.     while(  ch >= '0' && ch <= '9' )
  45.             n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
  46.     n=n*sign;
  47.   }
  48. #else
  49. inline void inp(int &n){
  50.  cin>>n;
  51. }
  52. #endif
  53. #define MAX 100001
  54. int ST[4*MAX];
  55. void update(int idx,int ss,int se,int index){
  56.   if(ss==se) {ST[idx]=1; return;}
  57.   int mid=(ss+se)>>1;
  58.   if(index<=mid) update(2*idx+1,ss,mid,index);
  59.   else update(2*idx+2,mid+1,se,index);
  60.   ST[idx]=ST[idx*2+1]+ST[2*idx+2];
  61. }
  62. int query_sum(int idx,int ss,int se,int l,int r){
  63.   if(ss>r||l>se) return 0;
  64.   if(l<=ss&&se<=r) return ST[idx];
  65.   int mid=(ss+se)>>1;
  66.   return query_sum(2*idx+1,ss,mid,l,r)+query_sum(2*idx+2,mid+1,se,l,r);
  67. }
  68. int query(int idx,int ss,int se,int index){
  69.   if(ss==se) return ss;
  70.   int mid=(ss+se)>>1;
  71.   if(ST[2*idx+1]>=index)
  72.    return query(2*idx+1,ss,mid,index);
  73.   return query(2*idx+2,mid+1,se,index-ST[2*idx+1]);
  74. }
  75.  
  76. int main(){
  77.  
  78.  // #ifndef ONLINE_JUDGE
  79.    // f_in("in.cpp");
  80. 	//f_out("out.cpp");
  81.  // #endif
  82.   int t=1;
  83.   //inp(t);
  84.   while(t--){
  85.    int n; inp(n);
  86.    VLL A(n);
  87.    VL B(n);
  88.    int i;
  89.    FOR(i,0,n) scanll(A[i].ft),B[i]=A[i].ft,A[i].sd=i;
  90.    sort(all(A));
  91.    int sum,idx;
  92.    ll ans=1;
  93.    for(i=n-1;i>=0;i--){
  94.       sum=query_sum(0,0,n-1,A[i].sd,n-1);
  95.       if(sum){
  96.          sum=query_sum(0,0,n-1,0,A[i].sd);
  97.          ans=ans*(B[query(0,0,n-1,sum+1)]);
  98.          ans%=MOD;
  99.       }
  100.       update(0,0,n-1,A[i].sd);
  101.   }
  102.   printll(ans);
  103.   }
  104.   return 0;
  105. }
  106.  
  107.  
Time limit exceeded #stdin #stdout 5s 4860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Bb2afR
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!