oj.uz

답안 #709662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709662 2023-03-14T07:00:33 Z swagchicken Zoltan (COCI16_zoltan) C++14
63 / 140
 299 ms 26980 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)%MOD << 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
63.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Incorrect 1 ms 340 KB Output isn't correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Correct 157 ms 21452 KB Output is correct
12 Correct 143 ms 18516 KB Output is correct
13 Correct 130 ms 17612 KB Output is correct
14 Incorrect 189 ms 18552 KB Output isn't correct
15 Incorrect 299 ms 23252 KB Output isn't correct
16 Incorrect 288 ms 26832 KB Output isn't correct
17 Incorrect 208 ms 26980 KB Output isn't correct
18 Incorrect 220 ms 26828 KB Output isn't correct
19 Incorrect 211 ms 26940 KB Output isn't correct
20 Incorrect 228 ms 26964 KB Output isn't correct