Submission #322046

#	Time	Username	Problem	Language	Result	Execution time	Memory
322046		gmyu	Zoltan (COCI16_zoltan)	C++14	21 / 140	414 ms	28016 KiB

zoltan

/*
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];
}

ll mypow[MAXV];

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();
    mypow[0] = 1;
    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_c = (inc_fg.inc_mc * dec_fg.dec_mc * mypow[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 * mypow[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;

}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:134:12: warning: unused variable 'j' [-Wunused-variable]
  134 |     int i, j, k;
      |            ^
zoltan.cpp:134:15: warning: unused variable 'k' [-Wunused-variable]
  134 |     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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 140