답안 #737222

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737222 2023-05-07T00:03:42 Z Olympia Zoltan (COCI16_zoltan) C++17
91 / 140
700 ms 40308 KB
#include <iostream>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <map>
#include <deque>
using namespace std;
const int MOD = 1e9 + 7;
struct SegmentTree {
    vector<pair<int,int64_t>> vec;
    pair<int,int64_t> id = make_pair(-1, 1);
    pair<int,int64_t> merge (pair<int,int64_t> left, pair<int,int64_t> right) {
        if (left.first == -1) return right;
        if (right.first == -1) return left;
        if (left.first > right.first) return left;
        if (left.first < right.first) return right;
        left.second += right.second;
        left.second %= MOD;
        return left;
    }   
    pair<int,int64_t> query (int dum, int tl, int tr, int l, int r) {
        if (tl >= l and tr <= r) {
            return vec[dum];
        } 
        if (r < tl or tr < l) {
            return id;
        }
        return merge(query(2 * dum + 1, tl, (tl + tr)/2, l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r));
    }
    pair<int,int64_t> query (int l, int r) {
        return query(0, 0, (int)vec.size()/2 - 1, l, r);
    }
    void update (int dum, pair<int,int64_t> node) {
        dum += (int)vec.size()/2 - 1;
        vec[dum] = node;
        while (dum != 0) {
            dum = (dum - 1)/2;
            vec[dum] = merge(vec[2 * dum + 1], vec[2 * dum + 2]);
        }
    }
    SegmentTree (int n) {
        n = (1 << (int)log2(n)) * 2;
        vec.assign(2 * n, id);
    }
};
SegmentTree st = SegmentTree(1);
vector<pair<int,int64_t>> lis (vector<int>& v) {
    st.vec.assign(st.vec.size(), st.id);
    map<int,vector<int>> oc;
    for (int i = 0; i < v.size(); i++) {
        oc[-v[i]].push_back(i);
    }
    vector<pair<int,int64_t>> vec;
    vec.push_back(make_pair(0, 1));
    int used = pow(2, v.size() - 1);
    for (auto& p: oc) {
        vector<pair<int,int64_t>> upd;
        for (int i: p.second) {
            pair<int,int64_t> node = st.query(i + 1, (int)v.size() - 1);
            if (node.first == -1) {
                node = make_pair(1, 1);
            } else {
                node.first += 1;
            }
            upd.push_back(node);
        }
        reverse(upd.begin(), upd.end());
        for (int i: p.second) {
            st.update(i, upd.back()), upd.pop_back();
        }
        pair<int,int64_t> g = st.id;
        for (int i: p.second) {
            g = st.merge(g, st.query(i, i));
        }
        vec.emplace_back(g);
    }
    return vec;
}
vector<pair<int,int64_t>> lds (vector<int>& v) {
    st.vec.assign(st.vec.size(), st.id);
    map<int,vector<int>> oc;
    for (int i = 0; i < v.size(); i++) {
        oc[v[i]].push_back(i);
    }
    vector<pair<int,int64_t>> vec;
    vec.push_back(make_pair(0, 1));
    for (auto& p: oc) {
        vector<pair<int,int64_t>> upd;
        for (int i: p.second) {
            pair<int,int64_t> node = st.query(i + 1, (int)v.size() - 1);
            if (node.first == -1) {
                node = make_pair(1, 1);
            } else {
                node.first += 1;
            }
            upd.push_back(node);
        }
        reverse(upd.begin(), upd.end());
        for (int i: p.second) {
            st.update(i, upd.back()), upd.pop_back();
        }
        vec.emplace_back(st.query(0, (int)v.size() - 1));
    }
    reverse(vec.begin(), vec.end());
    return vec;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    st = SegmentTree(n);
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    auto a1 = lds(v);
    auto a2 = lis(v);
    int64_t mx = 0, cnt = 0;
    for (int i = 0; i < a1.size(); i++) {
        if (a1[i].first + a2[i].first > mx) {
            mx = a1[i].first + a2[i].first;
            cnt = (a1[i].second * a2[i].second) % MOD;
            cnt %= MOD;
        } else if (a1[i].first + a2[i].first == mx) {
            cnt += (a1[i].second * a2[i].second) % MOD;
            cnt %= MOD;
        }
    }
    for (int i = 0; i < n - mx; i++) {
        cnt *= 2;
        cnt %= MOD;
    }
    if (cnt % 2 == 0) cnt /= 2;
    else cnt = (cnt + MOD)/2 % MOD;   
    cout << mx << " " << cnt;
}

Compilation message

zoltan.cpp: In function 'std::vector<std::pair<int, long int> > lis(std::vector<int>&)':
zoltan.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp:61:9: warning: unused variable 'used' [-Wunused-variable]
   61 |     int used = pow(2, v.size() - 1);
      |         ^~~~
zoltan.cpp: In function 'std::vector<std::pair<int, long int> > lds(std::vector<int>&)':
zoltan.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:126:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0; i < a1.size(); i++) {
      |                     ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 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 0 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Runtime error 343 ms 35096 KB Memory limit exceeded
12 Correct 304 ms 32296 KB Output is correct
13 Correct 256 ms 24076 KB Output is correct
14 Correct 436 ms 32484 KB Output is correct
15 Runtime error 580 ms 36792 KB Memory limit exceeded
16 Runtime error 700 ms 40308 KB Memory limit exceeded
17 Runtime error 460 ms 36520 KB Memory limit exceeded
18 Runtime error 540 ms 36352 KB Memory limit exceeded
19 Runtime error 486 ms 36452 KB Memory limit exceeded
20 Runtime error 458 ms 36372 KB Memory limit exceeded