oj.uz

Submission #62763

# Submission time Handle Problem Language Result Execution time Memory
62763 2018-07-30T02:56:44 Z jjwdi0 None (KOI18_matrix) C++11
23 / 100
 4000 ms 787456 KB 
#include <bits/stdc++.h>
#define ROOT 450
using namespace std;
using pr = pair<int, int>;
using tr = pair<int, pr>;
using ll = long long;

int R, N, ans;
pr A[200005];
tr B[200005];
vector<int> v;
int comp[200005];

struct seg_tree {
    int tree[555555], base;
    void init(int x) { for(base=1; base<x; base<<=1); for(int i=1; i<=base*2; i++) tree[i] = 0; }
    void update(int x, int y) {
        x += base - 1;
        tree[x] = y, x /= 2;
        while(x) tree[x] = max(tree[x*2], tree[x*2+1]), x /= 2;
    }
    int RMQ(int s, int e) {
        s += base - 1, e += base - 1;
        int res = 0;
        while(s < e) {
            if(s & 1) res = max(res, tree[s++]);
            if(!(e & 1)) res = max(res, tree[e--]);
            s >>= 1, e >>= 1;
        }
        if(s == e) res = max(res, tree[s]);
        return res;
    }
} S[ROOT];

vector<tr> bucket[ROOT];

int main() {
    scanf("%d %d", &R, &N);
    for(int i=0; i<=N/ROOT; i++) S[i].init(N);
    if(R == 2) {
        for(int i=1; i<=N; i++) scanf("%d", &A[i].first);
        for(int i=1; i<=N; i++) scanf("%d", &A[i].second);
        sort(A+1, A+N+1);
        for(int i=1; i<=N; i++) {
            auto it = lower_bound(v.begin(), v.end(), A[i].second);
            if(it == v.end()) v.push_back(A[i].second);
            else *it = A[i].second;
        }
        printf("%d\n", v.size());
    }
    else {
        for(int i=1; i<=N; i++) scanf("%d", &B[i].first);
        for(int i=1; i<=N; i++) scanf("%d", &B[i].second.first);
        for(int i=1; i<=N; i++) scanf("%d", &B[i].second.second);
        sort(B+1, B+N+1);
        for(int i=1; i<=N; i++) comp[i] = B[i].second.first;
        sort(comp+1, comp+N+1);
        for(int i=1; i<=N; i++) B[i].second.first = (int)( lower_bound(comp+1, comp+N+1, B[i].second.first) - comp );
        for(int i=1; i<=N; i++) comp[i] = B[i].second.second;
        sort(comp+1, comp+N+1);
        for(int i=1; i<=N; i++) B[i].second.second = (int)( lower_bound(comp+1, comp+N+1, B[i].second.second) - comp );

        int ans = 0;

        for(int i=1; i<=N; i++) {
            int idx = B[i].second.first / ROOT;
            int mx = 1;
            for(int j=0; j<idx; j++) {
                mx = max(mx, S[j].RMQ(1, B[i].second.second) + 1);
            }
            for(auto it : bucket[idx]) {
                if(it.second.first < B[i].second.first && it.second.second < B[i].second.second) mx = max(mx, it.first + 1);
            }
            bucket[idx].push_back(tr(mx, B[i].second));
            S[idx].update(B[i].second.second, mx);
            ans = max(ans, mx);
        }
        printf("%d\n", ans);
    }
}

Compilation message

matrix.cpp: In function 'int main()':
matrix.cpp:49:32: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
         printf("%d\n", v.size());
                        ~~~~~~~~^
matrix.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &R, &N);
     ~~~~~^~~~~~~~~~~~~~~~~
matrix.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &A[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:42:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &A[i].second);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~
matrix.cpp:52:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~
matrix.cpp:53:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].second.first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:54:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i=1; i<=N; i++) scanf("%d", &B[i].second.second);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3832 KB Output is correct
2 Correct 14 ms 4016 KB Output is correct
3 Correct 14 ms 4320 KB Output is correct
4 Correct 14 ms 4560 KB Output is correct
5 Correct 16 ms 4824 KB Output is correct
6 Correct 15 ms 5292 KB Output is correct
7 Correct 14 ms 5292 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5764 KB Output is correct
2 Correct 28 ms 6104 KB Output is correct
3 Correct 45 ms 6396 KB Output is correct
4 Correct 53 ms 6612 KB Output is correct
5 Correct 36 ms 6996 KB Output is correct
6 Correct 33 ms 7288 KB Output is correct
7 Correct 45 ms 7584 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3832 KB Output is correct
2 Correct 14 ms 4016 KB Output is correct
3 Correct 14 ms 4320 KB Output is correct
4 Correct 14 ms 4560 KB Output is correct
5 Correct 16 ms 4824 KB Output is correct
6 Correct 15 ms 5292 KB Output is correct
7 Correct 14 ms 5292 KB Output is correct
8 Runtime error 2153 ms 787456 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
9 Halted 0 ms 0 KB -

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5764 KB Output is correct
2 Correct 28 ms 6104 KB Output is correct
3 Correct 45 ms 6396 KB Output is correct
4 Correct 53 ms 6612 KB Output is correct
5 Correct 36 ms 6996 KB Output is correct
6 Correct 33 ms 7288 KB Output is correct
7 Correct 45 ms 7584 KB Output is correct
8 Execution timed out 4019 ms 787456 KB Time limit exceeded (wall clock)
9 Halted 0 ms 0 KB -