| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 997212 |
2024-06-11T20:32:12 Z |
TsotneSV |
Zoltan (COCI16_zoltan) |
C++17 |
|
148 ms |
65536 KB |
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
void fileIO(string filename) {
freopen((filename + ".in").c_str(), "r", stdin);
freopen((filename + ".out").c_str(), "w", stdout);
}
const ll MOD = 1000000007;
// const ll mod = 998244353;
// ll mod;
const int inf=1e9,MAXN=2e5+1;
const ll INF=1e18;
const ld pi = 3.14159265358979323846;
// typedef long long ll;
template<typename Node,typename Update>
struct Segtr {
int s;
vector<Node> tree;
void build(int v,int tl,int tr) {
if(tl == tr) {
tree[v] = Node(0);
}else {
int tm = (tl + tr)/2;
build(2*v,tl,tm); build(2*v+1,tm+1,tr);
tree[v].merge(tree[2*v],tree[2*v+1]);
}
}
void update(int v,int idx,int tl,int tr,Update addend) {
if(tl == tr) {
addend.apply(tree[v]);
}else {
int tm = (tl + tr)/2;
if(idx <= tm) update(2*v,idx,tl,tm,addend);
else update(2*v+1,idx,tm+1,tr,addend);
tree[v].merge(tree[2*v],tree[2*v+1]);
// dbg(tree[2*v].mx); dbg(tree[2*v+1].mx);
// dbg(tree[v].cnt);
}
}
Node query(int v,int l,int r,int tl,int tr) {
if(l > r) return Node(0); // *
else if(tl == l && tr == r) return tree[v];
int tm = (tl + tr)/2;
Node L,R,ans;
L = query(2*v,l,min(r,tm),tl,tm); R = query(2*v+1,max(l,tm+1),r,tm+1,tr);
ans.merge(L,R);
return ans;
}
Segtr(int n) {
s = n;
tree.resize(4*n);
build(1,0,n-1);
}
};
struct Node1 {
ll mx,cnt; // * shecvla sheidzleba
void merge(Node1 &a,Node1 &b) {
if(a.mx == 0) {
mx = b.mx;
cnt = b.cnt;
return;
}else if(b.mx == 0) {
mx = a.mx;
cnt = a.cnt;
return;
}
if(a.mx > b.mx) {
mx = a.mx;
cnt = a.cnt;
}else if(a.mx < b.mx) {
mx = b.mx;
cnt = b.cnt;
}else {
mx = a.mx;
cnt = (a.cnt % MOD + b.cnt % MOD) % MOD;
}
}
Node1() : mx(0),cnt(1) {}
Node1(int a) {
mx = a;
cnt = 1;
}
};
struct Update1 {
int val,cnt;
Update1(int val,int cnt) {
this->val = val;
this->cnt = cnt;
}
void apply(Node1 &a) {
if(val < a.mx) return;
else if(val > a.mx) {
a.mx = val;
a.cnt = cnt;
}else {
a.cnt = (a.cnt % MOD + cnt % MOD) % MOD;
}
}
};
int n;
ll binpow(int a,ll b) {
ll res = 1;
while(b) {
if(b&1) res = res * a % MOD;
a = a * a % MOD;
b/=2;
} return res;
}
void solve(int tc = 0){
cin>>n; int cnt = 0; vi inc,dec,A(n+1);
for(int i=1;i<=n;i++) {
cin>>A[i];
if(i > 1) {
if(A[i] == A[1]) cnt++;
else if(A[i] < A[1]) dec.pb(A[i]);
else inc.pb(A[i]);
}
} vi inc1 = inc,dec1 = dec;
map<int,int> cmp1,cmp2;
sort(all(inc1)); sort(all(dec1));
for(int i=0;i<sz(inc1);i++) cmp1[inc1[i]] = i;
for(int i=0;i<sz(dec1);i++) cmp2[dec1[i]] = i;
for(int &i : inc) i = cmp1[i];
for(int &i : dec) i = cmp2[i];
Segtr<Node1,Update1> T1(sz(cmp1) + 5),T2(sz(cmp2) + 5);
for(int i : inc) {
Node1 x = T1.query(1,0,i-1,0,sz(cmp1) -1);
T1.update(1,i,0,sz(cmp1)-1,Update1(x.mx + 1,x.cnt));
}
for(int i : dec) {
Node1 x = T2.query(1,i+1,sz(cmp2)-1,0,sz(cmp2)-1);
T2.update(1,i,0,sz(cmp2)-1,Update1(x.mx + 1,x.cnt));
}
int ans = T1.tree[1].mx + T2.tree[1].mx + 1;
cout<<ans<<" "<<((T1.tree[1].cnt * T2.tree[1].cnt % MOD) * binpow(2,n - ans) % MOD * (cnt + 1)) % MOD;
}
signed main(){
send help
int tc=1;
// cin>>tc;
for(int t = 0; t < tc; t++) solve(t);
}
Compilation message
zoltan.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
1 | #pragma gcc diagnostic "-std=c++1z"
|
zoltan.cpp: In function 'void fileIO(std::string)':
zoltan.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 11 |
Runtime error |
127 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Incorrect |
83 ms |
16980 KB |
Output isn't correct |
| 13 |
Runtime error |
107 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Incorrect |
119 ms |
17132 KB |
Output isn't correct |
| 15 |
Incorrect |
148 ms |
21204 KB |
Output isn't correct |
| 16 |
Runtime error |
129 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
111 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
102 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
102 ms |
65536 KB |
Execution killed with signal 9 |
