| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 997205 |
2024-06-11T20:18:29 Z |
TsotneSV |
Zoltan (COCI16_zoltan) |
C++17 |
|
165 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,vector<int> &arr) {
if(tl == tr) {
tree[v] = Node(arr[tl]);
}else {
int tm = (tl + tr)/2;
build(2*v,tl,tm,arr); build(2*v+1,tm+1,tr,arr);
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,vector<int> &arr) {
s = n;
tree.resize(4*n);
build(1,0,n-1,arr);
}
};
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 + b.cnt;
}
}
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 += cnt;
}
}
};
int n;
int pw[MAXN],A[MAXN];
void solve(int tc = 0){
cin>>n; int cnt = 0; vi inc,dec;
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+1;
for(int i=0;i<sz(dec1);i++) cmp2[dec1[i]] = i+1;
for(int &i : inc) i = cmp1[i];
for(int &i : dec) i = cmp2[i];
vi A(cmp1.size() + 10,0),B(cmp2.size() + 10,0);
Segtr<Node1,Update1> T1(sz(A),A),T2(sz(B),B);
for(int i : inc) {
Node1 x = T1.query(1,0,i-1,0,sz(A)-1);
T1.update(1,i,0,sz(A)-1,Update1(x.mx + 1,x.cnt));
}
for(int i : dec) {
Node1 x = T2.query(1,i+1,sz(B)-1,0,sz(B)-1);
T2.update(1,i,0,sz(B)-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) * pw[n - ans] % MOD * (cnt + 1)) % MOD;
}
signed main(){
pw[0] = 1;
for(int i=1;i<MAXN;i++) pw[i] = pw[i-1] * 2 % MOD;
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 |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
1112 KB |
Output is correct |
| 3 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1140 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
1372 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
1372 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
1372 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
1372 KB |
Output isn't correct |
| 11 |
Incorrect |
101 ms |
21024 KB |
Output isn't correct |
| 12 |
Incorrect |
84 ms |
18388 KB |
Output isn't correct |
| 13 |
Incorrect |
80 ms |
17328 KB |
Output isn't correct |
| 14 |
Incorrect |
104 ms |
18320 KB |
Output isn't correct |
| 15 |
Incorrect |
165 ms |
22564 KB |
Output isn't correct |
| 16 |
Incorrect |
158 ms |
27848 KB |
Output isn't correct |
| 17 |
Runtime error |
98 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
114 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
96 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
