| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 91752 |
2018-12-29T20:23:28 Z |
updown1 |
Zoltan (COCI16_zoltan) |
C++17 |
|
289 ms |
33792 KB |
/*
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], cop[MAXN], sm[MAXN], len, loc1[MAXN], loc2[MAXN], lispos[MAXN], ldspos[MAXN], olen;
vector<int> vals[MAXN];
/// vals is sorted
map<int, int> chg;
ll liscnt[MAXN], ldscnt[MAXN], ocnt;
vector<ll> ft[MAXN];
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 cop[i] = inp[i];
sort(cop, cop+N);
chg[cop[0]] = 0;
For (i, 1, N) if (cop[i] != cop[i-1]) {
chg[cop[i]] = 1+chg[cop[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 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, (ldscnt[i] * liscnt[i+1])%MOD);
}
int x = 1;
For (i, 0, N-olen) x = (2*x)%MOD;
w<< olen s (ocnt*x)%MOD<<e;
}
Compilation message
zoltan.cpp: In function 'void update(int, int, int)':
zoltan.cpp:31:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
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);}
~^~~~~~~~~~~~~~~~
zoltan.cpp: At global scope:
zoltan.cpp:35:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
zoltan.cpp: In function 'int main()':
zoltan.cpp:8:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define For(i, a, b) for(int i=a; i<b; i++)
zoltan.cpp:65:14:
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:65:9: note: in expansion of macro 'For'
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
^~~
zoltan.cpp:8:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define For(i, a, b) for(int i=a; i<b; i++)
zoltan.cpp:92:25:
For (i, 1, len+1) For (j, 1, ft[i].size()) {
~~~~~~~~~~~~~~~~~~
zoltan.cpp:92:20: note: in expansion of macro 'For'
For (i, 1, len+1) For (j, 1, ft[i].size()) {
^~~
zoltan.cpp:8:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define For(i, a, b) for(int i=a; i<b; i++)
^
zoltan.cpp:9:13: note: in expansion of macro 'For'
#define ffi For(i, 0, N)
^~~
zoltan.cpp:105:5: note: in expansion of macro 'ffi'
ffi sm[i+1] = MOD-1;
^~~
zoltan.cpp:107:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
len = 0;
^~~
zoltan.cpp:8:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define For(i, a, b) for(int i=a; i<b; i++)
zoltan.cpp:129:14:
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:129:9: note: in expansion of macro 'For'
For (j, 1, vals[i].size()) loc2[vals[i][j]] = j;
^~~
zoltan.cpp:8:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define For(i, a, b) for(int i=a; i<b; i++)
zoltan.cpp:155:25:
For (i, 1, len+1) For (j, 1, ft[i].size()) {
~~~~~~~~~~~~~~~~~~
zoltan.cpp:155:20: note: in expansion of macro 'For'
For (i, 1, len+1) For (j, 1, ft[i].size()) {
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9848 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 3 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 4 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 5 |
Correct |
9 ms |
9768 KB |
Output is correct |
| 6 |
Correct |
10 ms |
9720 KB |
Output is correct |
| 7 |
Incorrect |
10 ms |
9980 KB |
Output isn't correct |
| 8 |
Incorrect |
10 ms |
9976 KB |
Output isn't correct |
| 9 |
Correct |
11 ms |
9976 KB |
Output is correct |
| 10 |
Correct |
10 ms |
10104 KB |
Output is correct |
| 11 |
Runtime error |
208 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
220 ms |
33792 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 13 |
Correct |
210 ms |
32620 KB |
Output is correct |
| 14 |
Runtime error |
289 ms |
33792 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 15 |
Runtime error |
239 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
280 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
193 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
195 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
195 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
192 ms |
33792 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
