oj.uz

Submission #900979

# Submission time Handle Problem Language Result Execution time Memory
900979 2024-01-09T05:49:37 Z 8pete8 Zoltan (COCI16_zoltan) C++17
140 / 140
 187 ms 14424 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,ll>
#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
using namespace std;
//#define int long long
#define double long double
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
const int mod=1e9+7,mxn=2e5,lg=22,inf=1e18,minf=-1e18,Mxn=100000;
int val[mxn+10],n;
pii merg(pii a,pii b){
	if(a.f!=b.f||a.f==0||b.f==0)return max(a,b);
	else return {a.f,(b.s+a.s)%mod};
}
struct seg{
	pii seg[2*mxn+10];
	void update(int pos,pii val){
		pos+=n+1;
		seg[pos]=merg(seg[pos],val);
		for(int i=pos;i>0;i>>=1)seg[i>>1]=merg(seg[i],seg[i^1]);
	}
	pii qry(int l,int r){
		pii ans={0,0};
		for(l+=n+1,r+=n+1;l<=r;l>>=1,r>>=1){
			if(l&1)ans=merg(ans,seg[l++]);
			if(!(r&1))ans=merg(ans,seg[r--]);
		}
		return ans;
	}
	void init(){for(int i=0;i<=2*n+2;i++)seg[i]={0,1};}
}t[2];
int32_t main(){
	fastio
	cin>>n;
	vector<int>v(n);
	for(int i=0;i<n;i++)cin>>v[i],val[i]=v[i];
	sort(all(v));
	for(int i=0;i<n;i++)val[i]=lb(all(v),val[i])-v.begin()+1;
	t[0].init();
	t[1].init();
	pii ans={0,0};
	for(int i=n-1;i>=0;i--){
		pii cur=t[0].qry(0,val[i]-1),cur2=t[1].qry(val[i]+1,n+1);
		cur.f++;
		cur2.f++;
		ans=merg(ans,{cur.f+cur2.f-1,(cur.s*cur2.s)%mod});
		t[0].update(val[i],cur);
		t[1].update(val[i],cur2);
	}
	for(int i=0;i<n-ans.f;i++)ans.s=(ans.s*2)%mod;
	cout<<ans.f<<" "<<ans.s;
}

Compilation message

zoltan.cpp:37:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   37 | const int mod=1e9+7,mxn=2e5,lg=22,inf=1e18,minf=-1e18,Mxn=100000;
      |                                       ^~~~
zoltan.cpp:37:49: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   37 | const int mod=1e9+7,mxn=2e5,lg=22,inf=1e18,minf=-1e18,Mxn=100000;
      |                                                 ^~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 98 ms 13996 KB Output is correct
12 Correct 88 ms 13904 KB Output is correct
13 Correct 81 ms 11868 KB Output is correct
14 Correct 102 ms 13864 KB Output is correct
15 Correct 130 ms 14160 KB Output is correct
16 Correct 187 ms 14416 KB Output is correct
17 Correct 123 ms 14416 KB Output is correct
18 Correct 112 ms 14416 KB Output is correct
19 Correct 114 ms 14416 KB Output is correct
20 Correct 124 ms 14424 KB Output is correct