/*
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_mc + b.inc_mc;
}
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_mc + b.dec_mc;
}
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(l == r) { // leaf
seg[v] = (SEGNODE) {0, 0, 0, 0, 0};
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(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(l == r) { // leaf
seg[v] = seg[v] + val;
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];
}
ll mypow[MAXV];
int main() {
debug = false; submit = false;
if(submit) setIO("testName");
int i, j, k;
ll ans = 0, ans_s = 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();
mypow[0] = 1LL;
for(i=1; i<=N; i++) {
mypow[i] = (2LL * mypow[i-1]) % MOD;
}
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_s = (inc_fg.inc_mc * dec_fg.dec_mc)%MOD;
//ans_c = (inc_fg.inc_mc * dec_fg.dec_mc * mypow[N - ans])%MOD;
if(debug) cout << " new ans " << ans << " " << ans_s << endl;
} else if( ans == inc_fg.inc_m + dec_fg.dec_m -1) {
ans_s += (inc_fg.inc_mc * dec_fg.dec_mc)%MOD;
ans_s %= MOD;
//ans_c += (inc_fg.inc_mc * dec_fg.dec_mc * mypow[N - ans])%MOD;
//ans_c %= MOD;
if(debug) cout << " repeat ans " << ans << " " << ans_s << 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);
}
int ans_c = (ans_s * mypow[N - ans])%MOD;
cout << ans << " " << ans_c << endl;
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:128:12: warning: unused variable 'j' [-Wunused-variable]
128 | int i, j, k;
| ^
zoltan.cpp:128:15: warning: unused variable 'k' [-Wunused-variable]
128 | int i, j, k;
| ^
zoltan.cpp: In function 'void setIO(std::string)':
zoltan.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
52 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
364 KB |
Output is correct |
| 8 |
Correct |
2 ms |
364 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 10 |
Correct |
2 ms |
364 KB |
Output is correct |
| 11 |
Incorrect |
248 ms |
13152 KB |
Output isn't correct |
| 12 |
Incorrect |
206 ms |
12900 KB |
Output isn't correct |
| 13 |
Incorrect |
190 ms |
7652 KB |
Output isn't correct |
| 14 |
Incorrect |
263 ms |
12896 KB |
Output isn't correct |
| 15 |
Incorrect |
358 ms |
13408 KB |
Output isn't correct |
| 16 |
Incorrect |
399 ms |
13892 KB |
Output isn't correct |
| 17 |
Correct |
305 ms |
13792 KB |
Output is correct |
| 18 |
Correct |
301 ms |
13920 KB |
Output is correct |
| 19 |
Correct |
303 ms |
13848 KB |
Output is correct |
| 20 |
Correct |
307 ms |
13920 KB |
Output is correct |
