oj.uz

Submission #62782

# Submission time Handle Problem Language Result Execution time Memory
62782 2018-07-30T03:49:44 Z jjwdi0 None (KOI18_matrix) C++11
38 / 100
 4000 ms 10856 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];
vector<int> comp2[ROOT];

struct seg_tree {
    int tree[ROOT*4], 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);
    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=0; i<=N/ROOT; i++) S[i].init(ROOT);
        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++) comp2[B[i].second.first/ROOT].push_back(B[i].second.second);
        for(int i=0; i<=N/ROOT; i++) sort(comp2[i].begin(), comp2[i].end());

        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, (int)(upper_bound(comp2[j].begin(), comp2[j].end(), B[i].second.second) - comp2[j].begin()) ) + 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((int)(lower_bound(comp2[B[i].second.first/ROOT].begin(), comp2[B[i].second.first/ROOT].end(), B[i].second.second) - comp2[B[i].second.first/ROOT].begin()) + 1, 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:39: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: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].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.first);
                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
matrix.cpp:55: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 10 ms 376 KB Output is correct
2 Correct 10 ms 484 KB Output is correct
3 Correct 10 ms 688 KB Output is correct
4 Correct 10 ms 688 KB Output is correct
5 Correct 8 ms 688 KB Output is correct
6 Correct 11 ms 712 KB Output is correct
7 Correct 12 ms 712 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1036 KB Output is correct
2 Correct 19 ms 1040 KB Output is correct
3 Correct 38 ms 1040 KB Output is correct
4 Correct 38 ms 1044 KB Output is correct
5 Correct 28 ms 1092 KB Output is correct
6 Correct 28 ms 1092 KB Output is correct
7 Correct 38 ms 1112 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 376 KB Output is correct
2 Correct 10 ms 484 KB Output is correct
3 Correct 10 ms 688 KB Output is correct
4 Correct 10 ms 688 KB Output is correct
5 Correct 8 ms 688 KB Output is correct
6 Correct 11 ms 712 KB Output is correct
7 Correct 12 ms 712 KB Output is correct
8 Correct 118 ms 2156 KB Output is correct
9 Correct 149 ms 2204 KB Output is correct
10 Correct 163 ms 2540 KB Output is correct
11 Correct 126 ms 2540 KB Output is correct
12 Correct 155 ms 2540 KB Output is correct
13 Correct 117 ms 2808 KB Output is correct
14 Correct 121 ms 2808 KB Output is correct
15 Correct 149 ms 2808 KB Output is correct
16 Correct 149 ms 3368 KB Output is correct
17 Correct 117 ms 3368 KB Output is correct
18 Correct 140 ms 3368 KB Output is correct
19 Correct 112 ms 3368 KB Output is correct
20 Correct 115 ms 3368 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1036 KB Output is correct
2 Correct 19 ms 1040 KB Output is correct
3 Correct 38 ms 1040 KB Output is correct
4 Correct 38 ms 1044 KB Output is correct
5 Correct 28 ms 1092 KB Output is correct
6 Correct 28 ms 1092 KB Output is correct
7 Correct 38 ms 1112 KB Output is correct
8 Correct 2641 ms 10624 KB Output is correct
9 Correct 2134 ms 10716 KB Output is correct
10 Correct 2549 ms 10856 KB Output is correct
11 Correct 3206 ms 10856 KB Output is correct
12 Execution timed out 4027 ms 10856 KB Time limit exceeded
13 Halted 0 ms 0 KB -