oj.uz

Submission #900968

# Submission time Handle Problem Language Result Execution time Memory
900968 2024-01-09T05:42:10 Z 8pete8 Zoltan (COCI16_zoltan) C++17
98 / 140
 236 ms 34036 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,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
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,p[mxn+10];
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[4*mxn+10];
	void update(int l,int r,int node,int pos,pii val){
		if(l==r){
			seg[node]=merg(seg[node],val);
			return ;
		}
		int mid=l+(r-l)/2;
		if(pos<=mid)update(l,mid,node<<1,pos,val);
		else update(mid+1,r,(node<<1)^1,pos,val);
		seg[node]=merg(seg[node<<1],seg[(node<<1)^1]);
	}
	pii qry(int l,int r,int node,int ql,int qr){
		if(l>qr||r<ql)return {0,0};
		if(l>=ql&&r<=qr)return seg[node];
		int mid=l+(r-l)/2;
		return merg(qry(l,mid,node<<1,ql,qr),qry(mid+1,r,(node<<1)^1,ql,qr));
	}
	void init(){for(int i=0;i<=4*n;i++)seg[i]={0,1};}
}t[2];
pii dp[mxn+10][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];
	p[0]=1;
	for(int i=1;i<=n;i++)p[i]=(p[i-1]*2)%mod;
	sort(all(v));
	for(int i=0;i<n;i++)val[i]=lb(all(v),val[i])-v.begin()+1;
	pii l,r;
	t[0].init();
	t[1].init();
	pii ans={0,0};
	for(int i=n-1;i>=0;i--){
		pii cur=t[0].qry(0,n+1,1,0,val[i]-1),cur2=t[1].qry(0,n+1,1,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(0,n+1,1,val[i],cur);
		t[1].update(0,n+1,1,val[i],cur2);
	}
	ans.s=((p[n-ans.f]*ans.s)%mod);
	cout<<ans.f<<" "<<ans.s;
}

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 2 ms 8536 KB Output is correct
9 Correct 2 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 142 ms 28460 KB Output is correct
12 Correct 116 ms 27984 KB Output is correct
13 Correct 104 ms 25940 KB Output is correct
14 Correct 154 ms 28244 KB Output is correct
15 Runtime error 191 ms 33360 KB Memory limit exceeded
16 Runtime error 236 ms 34036 KB Memory limit exceeded
17 Runtime error 164 ms 33372 KB Memory limit exceeded
18 Runtime error 168 ms 33364 KB Memory limit exceeded
19 Runtime error 164 ms 33364 KB Memory limit exceeded
20 Runtime error 168 ms 33364 KB Memory limit exceeded