oj.uz

Submission #361611

# Submission time Handle Problem Language Result Execution time Memory
361611 2021-01-30T20:05:26 Z gratus907 None (KOI18_matrix) C++17
38 / 100
 2145 ms 634716 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 = 1000000007;
const int MAXC = 1000000007;

// max-dynamic-2seg
// msg555 impl, some modifications
int agg(int a, int b) {return max(a, b);}
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){}
        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 = agg(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 = agg(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 agg(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 agg(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; 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';
}

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

Subtask #1
14.0 / 14.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 32428 KB Output is correct
2 Correct 72 ms 32812 KB Output is correct
3 Correct 113 ms 32704 KB Output is correct
4 Correct 153 ms 32300 KB Output is correct
5 Correct 92 ms 32812 KB Output is correct
6 Correct 63 ms 32832 KB Output is correct
7 Correct 154 ms 32520 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 620 KB Output is correct
2 Correct 5 ms 620 KB Output is correct
3 Correct 5 ms 620 KB Output is correct
4 Correct 5 ms 748 KB Output is correct
5 Correct 5 ms 620 KB Output is correct
6 Correct 5 ms 1012 KB Output is correct
7 Correct 5 ms 748 KB Output is correct
8 Correct 105 ms 5476 KB Output is correct
9 Correct 101 ms 5392 KB Output is correct
10 Correct 103 ms 6500 KB Output is correct
11 Correct 74 ms 5348 KB Output is correct
12 Correct 99 ms 5348 KB Output is correct
13 Correct 125 ms 8932 KB Output is correct
14 Correct 99 ms 5348 KB Output is correct
15 Correct 73 ms 5348 KB Output is correct
16 Correct 129 ms 13668 KB Output is correct
17 Correct 125 ms 8932 KB Output is correct
18 Correct 101 ms 8292 KB Output is correct
19 Correct 98 ms 5492 KB Output is correct
20 Correct 102 ms 5348 KB Output is correct

Subtask #4
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 32428 KB Output is correct
2 Correct 72 ms 32812 KB Output is correct
3 Correct 113 ms 32704 KB Output is correct
4 Correct 153 ms 32300 KB Output is correct
5 Correct 92 ms 32812 KB Output is correct
6 Correct 63 ms 32832 KB Output is correct
7 Correct 154 ms 32520 KB Output is correct
8 Correct 2145 ms 634716 KB Output is correct
9 Runtime error 103 ms 17636 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -