oj.uz

Submission #410163

# Submission time Handle Problem Language Result Execution time Memory
410163 2021-05-22T06:48:59 Z egod1537 None (KOI18_matrix) C++14
100 / 100
 261 ms 28092 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pi;

struct Tuple {
    int a, b, c;
};
bool operator<(const Tuple& t1, const Tuple& t2) {
    if (t1.a != t2.a) return t1.a < t2.a;
    if (t1.b != t2.b) return t1.b < t2.b;
    return t1.c < t2.c;
}

vector<Tuple> arr;

int maxlis = 0;
int dp[200001];
//lis 그래프
struct Graph {
    set<pi> g[200001];

    void insert(int k, pi p) {
        auto pos = g[k].lower_bound(p);

        //prev가 없을 때
        if (pos == g[k].begin()) pos = (g[k].insert(p)).first;
        else {
            auto back = prev(pos);
            if (back->second > p.second) {
                if (back->first == p.first) g[k].erase(pos);
                pos = (g[k].insert(p)).first;
            }
        }

        if (pos != g[k].end()) {
            while (next(pos) != g[k].end()) {
                auto nxt = next(pos);
                if (pos->second <= nxt->second) g[k].erase(nxt);
                else break;
            }
        }
    }
    bool ok(int k, pi p) {
        auto pos = g[k].lower_bound(p);
        if (pos == g[k].begin()) return false;

        auto pr = prev(pos);
        return pr->second <= p.second;
    }
}g;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, m; cin >> n >> m;
    arr.resize(m);
    for (int i = 0; i < m; i++) cin >> arr[i].a;
    for (int i = 0; i < m; i++) cin >> arr[i].b;
    if (n == 3) for (int i = 0; i < m; i++) cin >> arr[i].c;

    sort(arr.begin(), arr.end());

    if (n == 2) {
        vector<int> dp;
        for (int i = 0; i < m; i++) {
            int idx = lower_bound(dp.begin(), dp.end(), arr[i].b) - dp.begin();
            if (idx == dp.size()) dp.push_back(arr[i].b);
            else dp[idx] = arr[i].b;
        }
        cout << dp.size();
    }
    else {
        int ans = 0;

        for (int i = 0; i < m; i++) {
            pi now = { arr[i].b, arr[i].c };

            //어떤 mid_lis가 가능하면 0 ~ mid lis가 가능하므로
            int lo = 1, hi = maxlis + 1;
            while (lo <= hi) {
                int mid = (lo + hi) / 2;

                if (g.ok(mid, now)) lo = mid + 1;
                else hi = mid - 1;
            }

            dp[i] = lo;
            g.insert(dp[i], now);
            ans = max(ans, dp[i]);
            maxlis = max(maxlis, dp[i]);
        }

        cout << ans;
    }

    return 0;
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             if (idx == dp.size()) dp.push_back(arr[i].b);
      |                 ~~~~^~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9936 KB Output is correct
2 Correct 10 ms 9988 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 10016 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 11 ms 10100 KB Output is correct
7 Correct 10 ms 10056 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10320 KB Output is correct
2 Correct 16 ms 10508 KB Output is correct
3 Correct 14 ms 10192 KB Output is correct
4 Correct 16 ms 10196 KB Output is correct
5 Correct 14 ms 10448 KB Output is correct
6 Correct 14 ms 10584 KB Output is correct
7 Correct 15 ms 10332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9936 KB Output is correct
2 Correct 10 ms 9988 KB Output is correct
3 Correct 11 ms 9984 KB Output is correct
4 Correct 11 ms 10016 KB Output is correct
5 Correct 10 ms 9984 KB Output is correct
6 Correct 11 ms 10100 KB Output is correct
7 Correct 10 ms 10056 KB Output is correct
8 Correct 92 ms 15880 KB Output is correct
9 Correct 87 ms 15944 KB Output is correct
10 Correct 86 ms 16252 KB Output is correct
11 Correct 88 ms 15888 KB Output is correct
12 Correct 85 ms 15944 KB Output is correct
13 Correct 87 ms 16508 KB Output is correct
14 Correct 88 ms 16136 KB Output is correct
15 Correct 80 ms 15816 KB Output is correct
16 Correct 82 ms 17076 KB Output is correct
17 Correct 94 ms 16460 KB Output is correct
18 Correct 88 ms 16528 KB Output is correct
19 Correct 89 ms 16196 KB Output is correct
20 Correct 88 ms 15884 KB Output is correct

Subtask #4
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10320 KB Output is correct
2 Correct 16 ms 10508 KB Output is correct
3 Correct 14 ms 10192 KB Output is correct
4 Correct 16 ms 10196 KB Output is correct
5 Correct 14 ms 10448 KB Output is correct
6 Correct 14 ms 10584 KB Output is correct
7 Correct 15 ms 10332 KB Output is correct
8 Correct 171 ms 22936 KB Output is correct
9 Correct 161 ms 21704 KB Output is correct
10 Correct 161 ms 25544 KB Output is correct
11 Correct 136 ms 27928 KB Output is correct
12 Correct 124 ms 18576 KB Output is correct
13 Correct 188 ms 24136 KB Output is correct
14 Correct 235 ms 20884 KB Output is correct
15 Correct 142 ms 24852 KB Output is correct
16 Correct 141 ms 24852 KB Output is correct
17 Correct 172 ms 21704 KB Output is correct
18 Correct 247 ms 19024 KB Output is correct
19 Correct 143 ms 18576 KB Output is correct
20 Correct 199 ms 21828 KB Output is correct
21 Correct 173 ms 24844 KB Output is correct
22 Correct 237 ms 19400 KB Output is correct
23 Correct 171 ms 21840 KB Output is correct
24 Correct 141 ms 18632 KB Output is correct
25 Correct 216 ms 20048 KB Output is correct
26 Correct 260 ms 28092 KB Output is correct
27 Correct 124 ms 18576 KB Output is correct
28 Correct 144 ms 24904 KB Output is correct
29 Correct 162 ms 21652 KB Output is correct
30 Correct 164 ms 21788 KB Output is correct
31 Correct 261 ms 28028 KB Output is correct
32 Correct 165 ms 21708 KB Output is correct