| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 322044 | gmyu | Zoltan (COCI16_zoltan) | C++14 | 0 ms | 0 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.
/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 1e9+7; //
const ll INF = 1e18; //
#define MAXV 200007
#define MAXE 200007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y;
int val;
int visited;
};
struct EDGE {
int from, to;
ll weight;
bool operator<(EDGE other) const { return weight < other.weight; }
};
/// code from USACO examples
void setIO(string name) {
ios_base::sync_with_stdio(0); cin.tie(0);
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;
int N;
int a[MAXV];
vi ua;
/// ------ Segment Treee --------
int Nseg[2];
struct SEGNODE {
int flag;
int inc_m, inc_mc, dec_m, dec_mc;
SEGNODE operator+(SEGNODE b) { /// seg operations
SEGNODE ret;
if(inc_m != b.inc_m) {
ret.inc_m = max(inc_m, b.inc_m);
ret.inc_mc = (inc_m > b.inc_m) ? inc_mc : b.inc_mc;
} else {
ret.inc_m = inc_m;
ret.inc_mc = inc_m + b.inc_m;
}
if(dec_m != b.dec_m) {
ret.dec_m = max(dec_m, b.dec_m);
ret.dec_mc = (dec_m > b.dec_m) ? dec_mc : b.dec_mc;
} else {
ret.dec_m = dec_m;
ret.dec_mc = dec_m + b.dec_m;
}
return ret;
}
};
SEGNODE seg[600007]; /// max 2e5 unique y, which needs 2^19 for Nseg
void buildSeg(int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(debug) cout << v << " " ;
if(l == r) { // leaf
seg[v] = (SEGNODE) {0, 0, 0, 0, 0};
if(debug) cout << v << "=" << ua[l] << " ";
return;
}
int mid = (l + r) / 2;
buildSeg(2*v, l, mid); buildSeg(2*v+1, mid+1, r);
seg[v] = seg[2*v] + seg[2*v+1];
}
void initSeg() {
/// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
Nseg[0] = 0;
Nseg[1] = ua.size()-1;
buildSeg();
}
SEGNODE querySeg(int qle, int qri, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(debug) cout << v << " " ;
if(ua[r] < qle || ua[l] > qri) return (SEGNODE) {0, 0, 0, 0, 0};
if(qle <= ua[l] && ua[r] <= qri) return seg[v];
int mid = (l + r) / 2;
return querySeg(qle, qri, 2*v, l, mid) + querySeg(qle, qri, 2*v+1, mid+1, r);
}
void updateSeg(int vtx, SEGNODE val, int v = 1, int l = Nseg[0], int r = Nseg[1]){
if(debug) cout << v << " " ;
if(l == r) { // leaf
seg[v].flag += val.flag;
seg[v].inc_m += val.inc_m; seg[v].inc_mc += val.inc_mc;
seg[v].dec_m += val.dec_m; seg[v].dec_mc += val.dec_mc;
return;
}
int mid = (l + r) / 2;
(vtx <= ua[mid]) ? updateSeg(vtx, val, 2*v, l, mid) : updateSeg(vtx, val, 2*v+1, mid+1, r);
seg[v] = seg[2*v] + seg[2*v+1];
}
int main() {
debug = false; submit = false;
if(submit) setIO("testName");
int i, j, k;
ll ans = 0, ans_c = 0;;
cin >> N ;
for(i=0; i<N; i++) {
cin >> a[i];
ua.pb(a[i]);
}
sort(ua.begin(), ua.end());
ua.erase(unique(ua.begin(), ua.end()), ua.end());
initSeg();
for(i=N-1; i>=0; i--) {
SEGNODE inc_fg = querySeg(a[i]+1, MX);
if(inc_fg.inc_m == 0) {
inc_fg.inc_m = 1; inc_fg.inc_mc = 1;
} else
inc_fg.inc_m++;
if(debug) cout << "inc " << inc_fg.inc_m << " " << inc_fg.inc_mc << endl;
SEGNODE dec_fg = querySeg(-1, a[i]-1);
if(dec_fg.dec_m == 0) {
dec_fg.dec_m = 1; dec_fg.dec_mc = 1;
} else
dec_fg.dec_m++;
if(debug) cout << "dec " << dec_fg.dec_m << " " << dec_fg.dec_mc << endl;
if(ans < inc_fg.inc_m + dec_fg.dec_m - 1) {
ans = inc_fg.inc_m + dec_fg.dec_m - 1;
ans_c = (inc_fg.inc_mc * dec_fg.dec_mc * (int) pow(2, N - ans))%MOD;
if(debug) cout << " new ans " << ans << " " << ans_c << endl;
} else if( ans == inc_fg.inc_m + dec_fg.dec_m -1) {
ans_c += inc_fg.inc_mc * dec_fg.dec_mc * (int) pow(2, N - ans);
ans_c %= MOD;
if(debug) cout << " repeat ans " << ans << " " << ans_c << endl;
}
SEGNODE m1;
m1.flag = 1;
m1.inc_m = inc_fg.inc_m; m1.inc_mc = inc_fg.inc_mc;
m1.dec_m = dec_fg.dec_m; m1.dec_mc = dec_fg.dec_mc;
updateSeg(a[i], m1);
}
cout << ans << " " << ans_c << endl;
}