oj.uz

답안 #709660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709660 2023-03-14T06:58:42 Z swagchicken Zoltan (COCI16_zoltan) C++14
42 / 140
 313 ms 28636 KB 
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  = 1000000007;
#define inf 1e18;
#define INF INT_MAX

long double PI = 4*atan(1);
long double eps = 1e-12;

template<class T>
class SegmentTree {
    private:
        int n;
        vector<T> A, st;

    int l(int p) { return 2*p; }
    int r(int p) { return 2*p+1; }

    T conquer(T a, T b) {
        if(a.ff == b.ff) {
          return {a.ff, (a.ss + b.ss) %MOD};
        }
        if(a.ff > b.ff) return a;
        return b;
    }


    T query(int p, int L, int R, int ql, int qr) {   // O(log n)
        if(qr < L || R < ql) return {-1, 0};                      // infeasible
        if ((ql <= L) && (R <= qr)) return st[p];      // found the segment
        int m = (L+R)/2;
        return conquer(query(l(p), L  , m, ql, qr),
                       query(r(p), m+1, R, ql, qr));
    }

    void update(int p, int L, int R, int i, T val) {
        if (L == R) {
            st[p] = conquer(st[p], val);
            return;
        }
        int m = (L + R)/2;
        if (i <= m)
            update(l(p), L, m, i, val);
        else
            update(r(p), m+1, R, i, val);
        st[p] = conquer(st[l(p)], st[r(p)]);
    }


    public:
        SegmentTree(int sz) : n(sz), st(4*n) {}

        void update(int i, T val) {
            update(1,0,n-1,i,val);
        }

        T query(int i, int j) {
            return query(1,0,n-1,i,j);
        }

};


int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    //ofstream cout("output.txt");
    //ifstream cin("input.txt");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif  

    int n; cin >> n;
    vi a(n); re(a);

    vi ac = a;
    sort(all(ac));
    ac.erase(unique(all(ac)), ac.end());
  //  pr(ac);

    SegmentTree<pair<ll, ll>> stlo(n+10);
    SegmentTree<pair<ll, ll>> sthi(n+10);

    ll ans = 0;
    ll best = 0;

    RFOR(i,n,0) {
      int idx = lower_bound(all(ac), a[i]) - ac.begin() + 1;
      pair<ll, ll> v1 = stlo.query(0, idx-1);
  //    cout << v1.ff << " " << v1.ss << endl;
      if(v1.ff == 0) v1.ss = 1;
      v1.ff++;

      stlo.update(idx, v1);
    
      pair<ll, ll> v2 = sthi.query(idx + 1, n+5);
     // cout << v2.ff << " " << v2.ss << endl;
      if(v2.ff == 0) v2.ss = 1;
      v2.ff++;

      sthi.update(idx, v2);

      if(v1.ff + v2.ff - 1 > best) {
        best= v1.ff + v2.ff - 1;
        ans = v1.ss * v2.ss;
        ans %= MOD;
      } else {
        ans += v1.ss * v2.ss;
        ans %= MOD;
      }

    }

    ll p2 = 1;
    FOR(i,0,n-best) {
      p2 *= 2; p2 %= MOD;
    }
    cout << best << " " << ans * p2 << endl;

    

    //auto stop = chrono::high_resolution_clock::now();
    //auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    //cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Subtask #1
42.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Incorrect 2 ms 468 KB Output isn't correct
8 Incorrect 1 ms 460 KB Output isn't correct
9 Incorrect 1 ms 468 KB Output isn't correct
10 Incorrect 1 ms 456 KB Output isn't correct
11 Incorrect 168 ms 22548 KB Output isn't correct
12 Incorrect 132 ms 19536 KB Output isn't correct
13 Incorrect 128 ms 18488 KB Output isn't correct
14 Incorrect 181 ms 19892 KB Output isn't correct
15 Incorrect 258 ms 24784 KB Output isn't correct
16 Incorrect 313 ms 28636 KB Output isn't correct
17 Incorrect 215 ms 28196 KB Output isn't correct
18 Incorrect 241 ms 28196 KB Output isn't correct
19 Incorrect 203 ms 28196 KB Output isn't correct
20 Incorrect 214 ms 28204 KB Output isn't correct