oj.uz

Submission #62784

# Submission time Handle Problem Language Result Execution time Memory
62784 2018-07-30T03:59:20 Z jjwdi0 None (KOI18_matrix) C++11
38 / 100
 4000 ms 10904 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;

// Fast IO

static char _buffer[131072];
static int _currentChar = 0;
static int _charsNumber = 0;

static inline int _read() {
    if(_currentChar == 131072) {
        _charsNumber = fread(_buffer, 1, 131072, stdin);
        _currentChar = 0;
    }
    return _buffer[_currentChar++];
}

int _c, _t;

static inline int s() {
    _c = _read();
    while(_c <= 32) _c = _read();
    _t = 0;
    while(_c > 32) {
        _t *= 10;
        _t += _c-'0';
        _c = _read();
    }
    return _t;
}

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;
        while(x / 2) {
            if(max(tree[x/2*2], tree[x/2*2+1]) != tree[x]) break;
            tree[x/2] = tree[x];
            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() {
    R = s(), N = s();
    if(R == 2) {
        for(int i=1; i<=N; i++) A[i].first = s();
        for(int i=1; i<=N; i++) A[i].second = s();
        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++) B[i].first = s();
        for(int i=1; i<=N; i++) B[i].second.first = s();
        for(int i=1; i<=N; i++) B[i].second.second = s();
        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:81: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());
                        ~~~~~~~~^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 6 ms 740 KB Output is correct
4 Correct 6 ms 744 KB Output is correct
5 Correct 5 ms 744 KB Output is correct
6 Correct 4 ms 776 KB Output is correct
7 Correct 5 ms 776 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1184 KB Output is correct
2 Correct 16 ms 1312 KB Output is correct
3 Correct 33 ms 1400 KB Output is correct
4 Correct 42 ms 1428 KB Output is correct
5 Correct 22 ms 1428 KB Output is correct
6 Correct 14 ms 1428 KB Output is correct
7 Correct 36 ms 1428 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 4 ms 740 KB Output is correct
3 Correct 6 ms 740 KB Output is correct
4 Correct 6 ms 744 KB Output is correct
5 Correct 5 ms 744 KB Output is correct
6 Correct 4 ms 776 KB Output is correct
7 Correct 5 ms 776 KB Output is correct
8 Correct 50 ms 2424 KB Output is correct
9 Correct 49 ms 2424 KB Output is correct
10 Correct 47 ms 2808 KB Output is correct
11 Correct 39 ms 2808 KB Output is correct
12 Correct 43 ms 2808 KB Output is correct
13 Correct 46 ms 3060 KB Output is correct
14 Correct 54 ms 3060 KB Output is correct
15 Correct 35 ms 3060 KB Output is correct
16 Correct 46 ms 3568 KB Output is correct
17 Correct 45 ms 3568 KB Output is correct
18 Correct 46 ms 3568 KB Output is correct
19 Correct 48 ms 3568 KB Output is correct
20 Correct 56 ms 3568 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1184 KB Output is correct
2 Correct 16 ms 1312 KB Output is correct
3 Correct 33 ms 1400 KB Output is correct
4 Correct 42 ms 1428 KB Output is correct
5 Correct 22 ms 1428 KB Output is correct
6 Correct 14 ms 1428 KB Output is correct
7 Correct 36 ms 1428 KB Output is correct
8 Correct 2916 ms 10768 KB Output is correct
9 Correct 2078 ms 10904 KB Output is correct
10 Correct 2599 ms 10904 KB Output is correct
11 Correct 2423 ms 10904 KB Output is correct
12 Execution timed out 4033 ms 10904 KB Time limit exceeded
13 Halted 0 ms 0 KB -