oj.uz

Submission #361623

# Submission time Handle Problem Language Result Execution time Memory
361623 2021-01-30T20:37:09 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 4000 ms 386400 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;
void solve_2();
int m, n;
int arr[3][202020];
set <int> s;
const int MAXR = 404040;
const int MAXC = 404040;

// max-dynamic-2seg
// msg555 impl, some modifications
struct Dynamic2DSeg
{
    struct Node
    {
        Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
        int l, r, v;
        Node *lc, *rc;
    };
    struct RowNode
    {
        RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
        Node rowRoot;
        RowNode *lc, *rc;
    };
    RowNode root;
    static void update2(Node *node, int idx, int dt)
    {
        int lo = node -> l;
        int hi = node -> r;
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
        {
            node -> v = dt;
            return;
        }
        Node *& next = idx < mid ? node -> lc : node -> rc;
        if (next == NULL)
            next = new Node(idx, idx + 1, dt);
        else if (next -> l <= idx && idx < next -> r)
            update2(next, idx, dt);
        else
        {
            do {
                (idx < mid ? hi : lo) = mid;
                mid = (lo + hi) / 2;
            } while ((idx < mid) == (next->l < mid));
            Node * nnode = new Node(lo, hi);
            (next->l < mid ? nnode->lc : nnode->rc) = next;
            next = nnode;

            update2(nnode, idx, dt);
        }
        node -> v = max(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
    }
    static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
    {
        int mid = (lo + hi) / 2;
        if (lo + 1 == hi)
            update2(&node -> rowRoot, idx, dt);
        else
        {
            RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
            (ridx < mid ? hi : lo) = mid;
            if (nnode == NULL)
                nnode = new RowNode();
            update1(nnode, lo, hi, ridx, idx, dt);
            dt = max(node->lc ? query2(&node->lc->rowRoot, idx, idx + 1) : 0,
                     node->rc ? query2(&node->rc->rowRoot, idx, idx + 1) : 0);
            update2(&node->rowRoot, idx, dt);
        }
    }
    static int query2(Node *node, int a, int b)
    {
        if (node == NULL || b <= node -> l || node -> r <= a)
            return 0;
        else if (a <= node -> l && node -> r <= b)
            return node -> v;
        return max(query2(node->lc, a, b), query2(node->rc, a, b));
    }
    static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
    {
        if (node == NULL || b1 <= lo || hi <= a1)
            return 0;
        else if (a1 <= lo && hi <= b1)
            return query2(&node->rowRoot, a2, b2);
        int mid = (lo + hi) / 2;
        return max(query1(node->lc, lo, mid, a1, b1, a2, b2),
                   query1(node->rc, mid, hi, a1, b1, a2, b2));
    }
    void update(int x, int y, int dt)
    {
        update1(&root, 0, MAXR, x, y, dt);
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
    }
} DSEG;

void solve_3()
{
    vector <pair<int, pii>> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], {arr[1][i], arr[2][i]}});
    sort(all(v));
    vector <int> ans(n, 0);
    for (int i = n-1; i >= 0; i--)
    {
        int cx = v[i].second.first;
        int cy = v[i].second.second;
        ans[i] = DSEG.query(cx+1, cy+1, 1e9+1, 1e9+1) + 1;
        DSEG.update(cx, cy, ans[i]);
    }
    int r = 0;
    for (auto it:ans)
        r = max(it, r);
    cout << r << '\n';
}

vector <int> compress;
int32_t main()
{
    usecppio
    cin >> m >> n;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            if (i)
                compress.push_back(arr[i][j]);
        }
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), compress.end());
    for (int i = 1; i < m; i++)
        for (int j = 0; j < n; j++)
            arr[i][j] = lower_bound(all(compress), arr[i][j]) - compress.begin();
    if (m == 2)
        solve_2();
    else solve_3();
}


void solve_2()
{
    vector <pii> v;
    for (int i = 0; i < n; i++)
        v.push_back({arr[0][i], arr[1][i]});
    sort(all(v));
    vector <int> vv;
    for (int i = 0; i < n; i++)
        vv.push_back(v[i].second);
    set <int> :: iterator it;
    for (int i = 0; i < n; i++)
    {
        s.insert(vv[i]);
        it = s.upper_bound(vv[i]);
        if (it != s.end())
            s.erase(it);
    }
    cout << s.size() << '\n';
}

Compilation message

matrix.cpp: In constructor 'Dynamic2DSeg::RowNode::RowNode()':
matrix.cpp:32:23: warning: 'Dynamic2DSeg::RowNode::rc' will be initialized after [-Wreorder]
   32 |         RowNode *lc, *rc;
      |                       ^~
matrix.cpp:31:14: warning:   'Dynamic2DSeg::Node Dynamic2DSeg::RowNode::rowRoot' [-Wreorder]
   31 |         Node rowRoot;
      |              ^~~~~~~
matrix.cpp:30:9: warning:   when initialized here [-Wreorder]
   30 |         RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC, 0){}
      |         ^~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 620 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 8 ms 620 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 7 ms 620 KB Output is correct
6 Correct 7 ms 1132 KB Output is correct
7 Correct 8 ms 796 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 19692 KB Output is correct
2 Correct 61 ms 19692 KB Output is correct
3 Correct 102 ms 19820 KB Output is correct
4 Correct 132 ms 19692 KB Output is correct
5 Correct 80 ms 19692 KB Output is correct
6 Correct 52 ms 19692 KB Output is correct
7 Correct 129 ms 19692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 620 KB Output is correct
2 Correct 7 ms 620 KB Output is correct
3 Correct 8 ms 620 KB Output is correct
4 Correct 7 ms 748 KB Output is correct
5 Correct 7 ms 620 KB Output is correct
6 Correct 7 ms 1132 KB Output is correct
7 Correct 8 ms 796 KB Output is correct
8 Correct 151 ms 6120 KB Output is correct
9 Correct 151 ms 6072 KB Output is correct
10 Correct 149 ms 7272 KB Output is correct
11 Correct 122 ms 6120 KB Output is correct
12 Correct 147 ms 6120 KB Output is correct
13 Correct 173 ms 9704 KB Output is correct
14 Correct 146 ms 6120 KB Output is correct
15 Correct 125 ms 6248 KB Output is correct
16 Correct 182 ms 14568 KB Output is correct
17 Correct 174 ms 9704 KB Output is correct
18 Correct 163 ms 9036 KB Output is correct
19 Correct 147 ms 6120 KB Output is correct
20 Correct 154 ms 6120 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 19692 KB Output is correct
2 Correct 61 ms 19692 KB Output is correct
3 Correct 102 ms 19820 KB Output is correct
4 Correct 132 ms 19692 KB Output is correct
5 Correct 80 ms 19692 KB Output is correct
6 Correct 52 ms 19692 KB Output is correct
7 Correct 129 ms 19692 KB Output is correct
8 Correct 1677 ms 386144 KB Output is correct
9 Correct 2111 ms 383652 KB Output is correct
10 Correct 1326 ms 386144 KB Output is correct
11 Correct 1077 ms 386144 KB Output is correct
12 Correct 2435 ms 378720 KB Output is correct
13 Correct 1458 ms 386400 KB Output is correct
14 Correct 3203 ms 385932 KB Output is correct
15 Correct 1101 ms 386320 KB Output is correct
16 Correct 1091 ms 386272 KB Output is correct
17 Correct 2153 ms 386144 KB Output is correct
18 Execution timed out 4091 ms 289752 KB Time limit exceeded
19 Halted 0 ms 0 KB -