| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 997231 |
2024-06-11T21:29:29 Z |
TsotneSV |
Zoltan (COCI16_zoltan) |
C++17 |
|
176 ms |
27064 KB |
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
using namespace std;
/* /\_/\
(= ._.)
/ > \>
*/
//#pragma comment(linker, "/stack:200000000")
// #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 = 1e9+7;
// 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();
}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]);
}
}
Node query(int v,int l,int r,int tl,int tr) {
if(l > r) return Node(); // *
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 > 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(0) {}
};
struct Update1 {
int val; ll cnt;
Update1(int val,ll cnt) {
this->val = val;
this->cnt = cnt;
}
void apply(Node1 &a) {
if(val > a.mx) {
a.mx = val;
a.cnt = cnt;
}else if(val == a.mx) {
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; vi A,v;
for(int i=0;i<n;i++) {
int tmp;
cin>>tmp;
A.pb(tmp);
v.pb(tmp);
} sort(all(v)); v.resize(unique(all(v)) - v.begin());
for(int i=0;i<n;i++) {
A[i] = lower_bound(all(v),A[i]) - v.begin() + 1;
}
Segtr<Node1,Update1> T1(sz(v) + 1),T2(sz(v) + 1);
int len = 0; ll cnt = 0;
for(int i=sz(A)-1;i>=0;i--) {
Node1 x1 = T1.query(1,0,A[i]-1,0,sz(v));
Node1 x2 = T2.query(1,A[i]+1,sz(v),0,sz(v));
x1.cnt = max(x1.cnt,1ll);
x2.cnt = max(x2.cnt,1ll);
int tLen = x1.mx + x2.mx + 1; ll tCnt = x1.cnt * x2.cnt % MOD;
if(tLen > len) {
len = tLen;
cnt = tCnt;
}else if(tLen == len) {
cnt = (cnt + tCnt) % MOD;
}
// ......
T1.update(1,A[i],0,sz(v),Update1(x1.mx + 1,x1.cnt));
T2.update(1,A[i],0,sz(v),Update1(x2.mx + 1,x2.cnt));
} cout<<len<<" "<<cnt * binpow(2,n - len) % MOD<<endl;
}
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:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen((filename + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((filename + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is 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 |
Incorrect |
111 ms |
21632 KB |
Output isn't correct |
| 12 |
Incorrect |
92 ms |
18880 KB |
Output isn't correct |
| 13 |
Incorrect |
86 ms |
17876 KB |
Output isn't correct |
| 14 |
Incorrect |
115 ms |
18876 KB |
Output isn't correct |
| 15 |
Incorrect |
157 ms |
23228 KB |
Output isn't correct |
| 16 |
Incorrect |
176 ms |
27064 KB |
Output isn't correct |
| 17 |
Incorrect |
123 ms |
22968 KB |
Output isn't correct |
| 18 |
Incorrect |
129 ms |
22988 KB |
Output isn't correct |
| 19 |
Incorrect |
120 ms |
22968 KB |
Output isn't correct |
| 20 |
Incorrect |
140 ms |
23184 KB |
Output isn't correct |
