| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 91754 | updown1 | Zoltan (COCI16_zoltan) | C++17 | 284 ms | 33792 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
scale down the input
find the lis and lds and count how many for every starting element
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, N)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e endl//"\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int long long
const int MAXN=200001, MOD = 1000000007;
///500,000,000
int N, inp[MAXN], sm[MAXN], len, loc1[MAXN], loc2[MAXN], lispos[MAXN], ldspos[MAXN], olen, ldscnt[MAXN], ocnt, liscnt[MAXN];
vector<int> vals[MAXN], ft[MAXN];
/// vals is sorted
map<int, int> chg;
void update(int y, int x, int v) {while(x<=ft[y].size()-1) ft[y][x]= (ft[y][x] + v)%MOD, x+=(x&-x);}
int query (int y, int x) { return x>0 ? (ft[y][x]+query(y, x-(x&-x)))%MOD:0;}
main() {
//ifstream cin("test.in");
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N;
ffi cin >> inp[i];
For (i, 0, (N+1)/2) swap(inp[i], inp[N-1-i]);
ffi loc1[i] = inp[i];
sort(loc1, loc1+N);
chg[loc1[0]] = 0;
For (i, 1, N) if (loc1[i] != loc1[i-1]) {
chg[loc1[i]] = 1+chg[loc1[i-1]];
}
ffi inp[i] = chg[inp[i]];
//ffi w<< inp[i] << " "; w<<e;
For (i, 0, N+1) {vals[i].pb(MAXN-1); ft[i].pb(0);}
ffi {
/// find ind w sm[ind] > inp[i]
int a = 0, b = N;
while (a != b) {
int mid = (a+b+1)/2;
if (sm[mid] > inp[i]) a = mid;
else b = mid-1;
}
a++;
loc1[i] = a;
vals[a].pb(i); sm[a] = inp[i]; ft[a].pb(0);
len = max(len, a);
//w<< "added" s inp[i] s "to" s loc1[i]<<e;
}
For (i, 1, len+1) {
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
}
//w<< len<<e; For (i, 0, len+1) {w<< i << ":"; for (int j: vals[i]) w s j; w<<e;}
ffi {
/// turn on inp[i]
if (loc1[i] == 1) {
/// set to 1
update(loc1[i], loc2[i], 1);
}
else {
/// binary search and suffix sum
int k = loc1[i];
//w<< inp[vals[k-1][vals[k-1].size()-1]] s inp[i]<<e;
if (inp[vals[k-1][vals[k-1].size()-1]] <= inp[i]) continue; /// stays at 0
/// find vals[k-1][ind] > inp[i]
int a = 1, b = vals[k-1].size()-1;
while (a != b) {
int mid = (a+b)/2;
if (inp[vals[k-1][mid]] < inp[i]) a = mid+1;
else b = mid;
}
//w<< "updating" s inp[i]<<e;
update(k, loc2[i], (query(k-1, ft[k-1].size()-1) - query(k-1, a-1)+MOD)%MOD);
}
}
//For (i, 1, len+1) {w<< i << ":"; for (int j: vals[i]) w s inp[j]; w<<e;}
//For (i, 1, len+1) {w<< i << ":"; For (j, 1, ft[i].size()) w s query(i, j)-query(i, j-1); w<<e;}
For (i, 1, len+1) For (j, 1, ft[i].size()) {
if (lispos[inp[vals[i][j]]] < i) liscnt[inp[vals[i][j]]] = 0;
lispos[inp[vals[i][j]]] = i;
liscnt[inp[vals[i][j]]] += (query(i, j)-query(i, j-1)+MOD)%MOD;
}
for (int i=N-2; i>=0; i--) {
if (lispos[i] == lispos[i+1]) liscnt[i] = (liscnt[i] + liscnt[i+1])%MOD;
else if (lispos[i+1] > lispos[i]) {lispos[i] = lispos[i+1]; liscnt[i] = liscnt[i+1];}
}
//ffi w<< lispos[i] s liscnt[i]<<e;
/// Repeat for lds :(
ffi sm[i+1] = MOD-1;
//ffi w<< inp[i] << " "; w<<e;
len = 0;
For (i, 0, N+1) vals[i].clear(), ft[i].clear();
ffi {
/// find ind w sm[ind] < inp[i]
int a = 0, b = N;
while (a != b) {
int mid = (a+b+1)/2;
if (sm[mid] < inp[i]) a = mid;
else b = mid-1;
}
a++;
loc1[i] = a;
vals[a].pb(i); sm[a] = inp[i]; ft[a].pb(0);
len = max(len, a);
//w<< "added" s inp[i] s "to" s a<<e;
}
For (i, 0, N+1) {vals[i].pb(MAXN-1); ft[i].pb(0);}
For (i, 1, len+1) reverse(vals[i].begin(), vals[i].end());
For (i, 1, len+1) {
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
}
//w<< len<<e; For (i, 0, len+1) {w<< i << ":"; for (int j: vals[i]) w s j; w<<e;}
ffi {
/// turn on inp[i]
if (loc1[i] == 1) {
/// set to 1
update(loc1[i], loc2[i], 1);
}
else {
/// binary search and suffix sum
int k = loc1[i];
if (inp[vals[k-1][0]] >= inp[i]) continue; /// stays at 0
/// find vals[k-1][ind] < inp[i]
int a = 1, b = vals[k-1].size()-1;
while (a != b) {
int mid = (a+b+1)/2;
if (inp[vals[k-1][mid]] < inp[i]) a = mid;
else b = mid-1;
}
//w<< "updating" s inp[i]<<e;
update(k, loc2[i], query(k-1, a)%MOD);
}
}
//For (i, 1, len+1) {w<< i << ":"; For (j, 1, vals[i].size()) w s inp[vals[i][j]]; w<<e;}
//For (i, 1, len+1) {w<< i << ":"; For (j, 1, ft[i].size()) w s query(i, j)-query(i, j-1); w<<e;}
For (i, 1, len+1) For (j, 1, ft[i].size()) {
if (ldspos[inp[vals[i][j]]] < i) ldscnt[inp[vals[i][j]]] = 0;
ldspos[inp[vals[i][j]]] = i;
ldscnt[inp[vals[i][j]]] += (query(i, j)-query(i, j-1)+MOD)%MOD;
}
For (i, 1, N) {
if (ldspos[i] == ldspos[i-1]) ldscnt[i] = (ldscnt[i] + ldscnt[i-1])%MOD;
else if (ldspos[i-1] > ldspos[i]) {ldspos[i] = ldspos[i-1]; ldscnt[i] = ldscnt[i-1];}
}
//ffi w<< ldspos[i] s ldscnt[i]<<e;
//ffi if (liscnt[i] < 0 || ldscnt[i] < 0) w<< lispos[i] s liscnt[i] c ldspos[i] s ldscnt[i]<<e;
olen = max(ldspos[N-1], lispos[0]);
For (i, 0, N-1) olen = max(olen, ldspos[i] + lispos[i+1]);
if (ldspos[N-1] == olen) ocnt = ldscnt[N-1];
if (lispos[0] == olen) ocnt = max(ocnt, liscnt[0]);
For (i, 0, N-1) if (olen == ldspos[i] + lispos[i+1]) {
ocnt = max(ocnt, (int)(((ll)ldscnt[i] * liscnt[i+1])%MOD));
}
ll x = 1;
For (i, 0, N-olen) x = (2*x)%MOD;
w<< olen s (ocnt*x)%MOD<<e;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||