oj.uz

Submission #274158

# Submission time Handle Problem Language Result Execution time Memory
274158 2020-08-19T09:00:48 Z ne4eHbKa Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 540904 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define ft first
#define sd second
#define _ <<' '<<

//void* MEM = malloc(400 << 20);
//
//void* operator new(const size_t f) {
//    void* res = MEM;
//    MEM += f;
//    return res;
//}
//
//void operator delete(void*) {}

//#pragma GCC optimize("Ofast,O3")

namespace S {

//#include <ext/pb_ds/assoc_container.hpp>

//typedef __gnu_pbds::cc_hash_table<int, int> ht;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vv;
typedef pair<int, int> pii;

const int N = 2505;

int n, m;
list<int> l[N][N], u[N][N];
int p[N], length[N], la[N];
unordered_map<int, int> fl[N];
vector<bool> mk;
int c[5 * N], cn, xn, yn;
pii x[N], y[N];

int f[N * 5], fmax;
void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); }
void fadd(int i) { for(i = fmax - i; i <= fmax; i += i & -i) f[i]++; }
int fget(int i) { int v{}; for(i = fmax - i; i; i -= i & -i) v += f[i]; return v; }

int get(unordered_map<int, int> &a, int b) {
    const auto f = a.find(b);
    if(f == a.end()) return 0;
    return f->sd;
}

ll solve() {
    ll ans = 0;
    unordered_map<int, int> cl, fu, cu;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            swap(cl, fl[j]);
            for(const int &t : l[i][j])
                fl[j][t] = get(cl, t) + 1;
            cl.clear();
            swap(cu, fu);
            for(const int &t : u[i][j])
                fu[t] = get(cu, t) + 1;
            cu.clear();
            const auto &a = fl[j], &b = fu;
            if(a.size() * b.size() < 5) {
                for(const auto &i : a)
                    for(const auto &j : b)
                        ans += i.ft <= j.sd && j.ft <= i.sd;
                continue;
            }
            cn = 0;
            for(const auto &i : a) {
                c[cn++] = i.ft;
                c[cn++] = i.sd;
            }
            for(const auto &i : b) {
                c[cn++] = i.ft;
                c[cn++] = i.sd;
            }
            sort(c, c + cn);
            cn = unique(c, c + cn) - c;
            xn = yn = 0;
            finit(cn);
            auto find = [&] (const int &z) {return lower_bound(c, c + cn, z) - c;};
            for(const auto &i : a) x[xn++] = {find(i.sd), find(i.ft)};
            for(const auto &i : b) y[yn++] = {find(i.ft), find(i.sd)};
            sort(x, x + xn);
            sort(y, y + yn);
            int it = 0;
            for(int i = 0; i < xn; ++i) {
                for(; it < yn && y[it].ft <= x[i].ft; ++it)
                    fadd(y[it].sd);
                ans += fget(x[i].sd);
            }
        }
        fu.clear();
    }
    return ans;
}

int last(int i) {
    return la[i] == i ? i : la[i] = last(la[i]);
}

void unite(int i, int j) {
    i = last(i), j = last(j);
    length[j] += length[i];
    la[i] = j;
}

}

S::ll count_rectangles(S::vv a) {
    using namespace S;
    n = a.size();
    m = a[0].size();
    for(int i = 0; i < n; ++i) {
        iota(p, p + m, 0);
        iota(la, la + m, 0);
        mk.assign(m, false);
        sort(p, p + m, [&] (const int &fi, const int &se) {return a[i][fi] < a[i][se];});
        for(int t = 0; t < m; ) {
            int v = a[i][p[t]];
            list<int> f;
            for(; t < m && a[i][p[t]] == v; ++t) {
                int j = p[t];
                mk[j] = true;
                length[j] = 1;
                f.push_back(j);
                if(j + 1 < m && mk[j + 1]) unite(j, j + 1);
                if(j && mk[j - 1]) unite(j - 1, j);
            }
            for(int i : f) mk[last(i)] = false;
            for(int j : f) {
                j = last(j);
                if(mk[j]) continue;
                mk[j] = true;
                if(i == 0 || i == n - 1) continue;
                if(j == m - 1 || length[j] == j + 1) continue;
                l[i][j].push_back(length[j]);
            }
        }
    }
    for(int j = 0; j < m; ++j) {
        iota(p, p + n, 0);
        iota(la, la + n, 0);
        mk.assign(n, false);
        sort(p, p + n, [&] (const int &fi, const int &se) {return a[fi][j] < a[se][j];});
        for(int t = 0; t < n; ) {
            int v = a[p[t]][j];
            list<int> f;
            for(; t < n && a[p[t]][j] == v; ++t) {
                int i = p[t];
                mk[i] = true;
                length[i] = 1;
                f.push_back(i);
                if(i + 1 < n && mk[i + 1]) unite(i, i + 1);
                if(i && mk[i - 1]) unite(i - 1, i);
            }
            for(int j : f) mk[last(j)] = false;
            for(int i : f) {
                i = last(i);
                if(mk[i]) continue;
                mk[i] = true;
                if(j == 0 || j == m - 1) continue;
                if(i == n - 1 || length[i] == i + 1) continue;
                u[i][j].push_back(length[i]);
            }
        }
    }
    return solve();
}

#undef ft
#undef sd
#undef _

Compilation message

rect.cpp: In function 'void S::finit(int)':
rect.cpp:42:46: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 | void finit(int n) { fmax = n; memset(f, 0, n + 1 << 2); }
      |                                            ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 295160 KB Output is correct
2 Correct 203 ms 295248 KB Output is correct
3 Correct 208 ms 295396 KB Output is correct
4 Correct 205 ms 295288 KB Output is correct
5 Correct 199 ms 295160 KB Output is correct
6 Correct 203 ms 295300 KB Output is correct
7 Correct 203 ms 295160 KB Output is correct
8 Correct 202 ms 295288 KB Output is correct
9 Correct 209 ms 295160 KB Output is correct
10 Correct 238 ms 295160 KB Output is correct
11 Correct 211 ms 295288 KB Output is correct
12 Correct 206 ms 295160 KB Output is correct
13 Correct 229 ms 295160 KB Output is correct
14 Correct 198 ms 295160 KB Output is correct
15 Correct 201 ms 295176 KB Output is correct
16 Correct 212 ms 295160 KB Output is correct
17 Correct 210 ms 295208 KB Output is correct
18 Correct 212 ms 295144 KB Output is correct
19 Correct 212 ms 295236 KB Output is correct
20 Correct 203 ms 295144 KB Output is correct
21 Correct 203 ms 295116 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 295160 KB Output is correct
2 Correct 203 ms 295248 KB Output is correct
3 Correct 208 ms 295396 KB Output is correct
4 Correct 205 ms 295288 KB Output is correct
5 Correct 199 ms 295160 KB Output is correct
6 Correct 203 ms 295300 KB Output is correct
7 Correct 203 ms 295160 KB Output is correct
8 Correct 202 ms 295288 KB Output is correct
9 Correct 209 ms 295160 KB Output is correct
10 Correct 238 ms 295160 KB Output is correct
11 Correct 211 ms 295288 KB Output is correct
12 Correct 206 ms 295160 KB Output is correct
13 Correct 229 ms 295160 KB Output is correct
14 Correct 198 ms 295160 KB Output is correct
15 Correct 201 ms 295176 KB Output is correct
16 Correct 212 ms 295160 KB Output is correct
17 Correct 206 ms 295672 KB Output is correct
18 Correct 214 ms 295800 KB Output is correct
19 Correct 210 ms 295788 KB Output is correct
20 Correct 222 ms 295520 KB Output is correct
21 Correct 212 ms 295544 KB Output is correct
22 Correct 214 ms 295544 KB Output is correct
23 Correct 224 ms 295668 KB Output is correct
24 Correct 214 ms 295288 KB Output is correct
25 Correct 210 ms 295208 KB Output is correct
26 Correct 212 ms 295144 KB Output is correct
27 Correct 212 ms 295236 KB Output is correct
28 Correct 203 ms 295144 KB Output is correct
29 Correct 203 ms 295116 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 295160 KB Output is correct
2 Correct 203 ms 295248 KB Output is correct
3 Correct 208 ms 295396 KB Output is correct
4 Correct 205 ms 295288 KB Output is correct
5 Correct 199 ms 295160 KB Output is correct
6 Correct 203 ms 295300 KB Output is correct
7 Correct 203 ms 295160 KB Output is correct
8 Correct 202 ms 295288 KB Output is correct
9 Correct 209 ms 295160 KB Output is correct
10 Correct 238 ms 295160 KB Output is correct
11 Correct 211 ms 295288 KB Output is correct
12 Correct 206 ms 295160 KB Output is correct
13 Correct 229 ms 295160 KB Output is correct
14 Correct 198 ms 295160 KB Output is correct
15 Correct 201 ms 295176 KB Output is correct
16 Correct 212 ms 295160 KB Output is correct
17 Correct 206 ms 295672 KB Output is correct
18 Correct 214 ms 295800 KB Output is correct
19 Correct 210 ms 295788 KB Output is correct
20 Correct 222 ms 295520 KB Output is correct
21 Correct 212 ms 295544 KB Output is correct
22 Correct 214 ms 295544 KB Output is correct
23 Correct 224 ms 295668 KB Output is correct
24 Correct 214 ms 295288 KB Output is correct
25 Correct 245 ms 298360 KB Output is correct
26 Correct 243 ms 298348 KB Output is correct
27 Correct 240 ms 298304 KB Output is correct
28 Correct 231 ms 296440 KB Output is correct
29 Correct 243 ms 297848 KB Output is correct
30 Correct 256 ms 297848 KB Output is correct
31 Correct 242 ms 297688 KB Output is correct
32 Correct 244 ms 297848 KB Output is correct
33 Correct 210 ms 295208 KB Output is correct
34 Correct 212 ms 295144 KB Output is correct
35 Correct 212 ms 295236 KB Output is correct
36 Correct 203 ms 295144 KB Output is correct
37 Correct 203 ms 295116 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 295160 KB Output is correct
2 Correct 203 ms 295248 KB Output is correct
3 Correct 208 ms 295396 KB Output is correct
4 Correct 205 ms 295288 KB Output is correct
5 Correct 199 ms 295160 KB Output is correct
6 Correct 203 ms 295300 KB Output is correct
7 Correct 203 ms 295160 KB Output is correct
8 Correct 202 ms 295288 KB Output is correct
9 Correct 209 ms 295160 KB Output is correct
10 Correct 238 ms 295160 KB Output is correct
11 Correct 211 ms 295288 KB Output is correct
12 Correct 206 ms 295160 KB Output is correct
13 Correct 229 ms 295160 KB Output is correct
14 Correct 198 ms 295160 KB Output is correct
15 Correct 201 ms 295176 KB Output is correct
16 Correct 212 ms 295160 KB Output is correct
17 Correct 206 ms 295672 KB Output is correct
18 Correct 214 ms 295800 KB Output is correct
19 Correct 210 ms 295788 KB Output is correct
20 Correct 222 ms 295520 KB Output is correct
21 Correct 212 ms 295544 KB Output is correct
22 Correct 214 ms 295544 KB Output is correct
23 Correct 224 ms 295668 KB Output is correct
24 Correct 214 ms 295288 KB Output is correct
25 Correct 245 ms 298360 KB Output is correct
26 Correct 243 ms 298348 KB Output is correct
27 Correct 240 ms 298304 KB Output is correct
28 Correct 231 ms 296440 KB Output is correct
29 Correct 243 ms 297848 KB Output is correct
30 Correct 256 ms 297848 KB Output is correct
31 Correct 242 ms 297688 KB Output is correct
32 Correct 244 ms 297848 KB Output is correct
33 Correct 568 ms 314496 KB Output is correct
34 Correct 499 ms 314512 KB Output is correct
35 Correct 523 ms 317144 KB Output is correct
36 Correct 442 ms 314456 KB Output is correct
37 Correct 593 ms 334140 KB Output is correct
38 Correct 617 ms 334236 KB Output is correct
39 Correct 608 ms 334156 KB Output is correct
40 Correct 567 ms 331680 KB Output is correct
41 Correct 406 ms 306680 KB Output is correct
42 Correct 449 ms 310904 KB Output is correct
43 Correct 760 ms 328900 KB Output is correct
44 Correct 763 ms 329428 KB Output is correct
45 Correct 490 ms 312124 KB Output is correct
46 Correct 466 ms 312192 KB Output is correct
47 Correct 777 ms 326648 KB Output is correct
48 Correct 665 ms 326776 KB Output is correct
49 Correct 210 ms 295208 KB Output is correct
50 Correct 212 ms 295144 KB Output is correct
51 Correct 212 ms 295236 KB Output is correct
52 Correct 203 ms 295144 KB Output is correct
53 Correct 203 ms 295116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 295532 KB Output is correct
2 Correct 206 ms 295572 KB Output is correct
3 Correct 212 ms 295288 KB Output is correct
4 Correct 207 ms 295160 KB Output is correct
5 Correct 205 ms 295664 KB Output is correct
6 Correct 231 ms 295544 KB Output is correct
7 Correct 236 ms 295420 KB Output is correct
8 Correct 232 ms 295416 KB Output is correct
9 Correct 258 ms 295544 KB Output is correct
10 Correct 218 ms 295160 KB Output is correct
11 Correct 235 ms 295288 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 295160 KB Output is correct
2 Correct 1502 ms 362488 KB Output is correct
3 Correct 3504 ms 441380 KB Output is correct
4 Correct 3113 ms 442028 KB Output is correct
5 Correct 3368 ms 442144 KB Output is correct
6 Correct 984 ms 319516 KB Output is correct
7 Correct 1786 ms 341496 KB Output is correct
8 Correct 1901 ms 344440 KB Output is correct
9 Correct 210 ms 295208 KB Output is correct
10 Correct 212 ms 295144 KB Output is correct
11 Correct 212 ms 295236 KB Output is correct
12 Correct 203 ms 295144 KB Output is correct
13 Correct 203 ms 295116 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 295160 KB Output is correct
2 Correct 203 ms 295248 KB Output is correct
3 Correct 208 ms 295396 KB Output is correct
4 Correct 205 ms 295288 KB Output is correct
5 Correct 199 ms 295160 KB Output is correct
6 Correct 203 ms 295300 KB Output is correct
7 Correct 203 ms 295160 KB Output is correct
8 Correct 202 ms 295288 KB Output is correct
9 Correct 209 ms 295160 KB Output is correct
10 Correct 238 ms 295160 KB Output is correct
11 Correct 211 ms 295288 KB Output is correct
12 Correct 206 ms 295160 KB Output is correct
13 Correct 229 ms 295160 KB Output is correct
14 Correct 198 ms 295160 KB Output is correct
15 Correct 201 ms 295176 KB Output is correct
16 Correct 212 ms 295160 KB Output is correct
17 Correct 206 ms 295672 KB Output is correct
18 Correct 214 ms 295800 KB Output is correct
19 Correct 210 ms 295788 KB Output is correct
20 Correct 222 ms 295520 KB Output is correct
21 Correct 212 ms 295544 KB Output is correct
22 Correct 214 ms 295544 KB Output is correct
23 Correct 224 ms 295668 KB Output is correct
24 Correct 214 ms 295288 KB Output is correct
25 Correct 245 ms 298360 KB Output is correct
26 Correct 243 ms 298348 KB Output is correct
27 Correct 240 ms 298304 KB Output is correct
28 Correct 231 ms 296440 KB Output is correct
29 Correct 243 ms 297848 KB Output is correct
30 Correct 256 ms 297848 KB Output is correct
31 Correct 242 ms 297688 KB Output is correct
32 Correct 244 ms 297848 KB Output is correct
33 Correct 568 ms 314496 KB Output is correct
34 Correct 499 ms 314512 KB Output is correct
35 Correct 523 ms 317144 KB Output is correct
36 Correct 442 ms 314456 KB Output is correct
37 Correct 593 ms 334140 KB Output is correct
38 Correct 617 ms 334236 KB Output is correct
39 Correct 608 ms 334156 KB Output is correct
40 Correct 567 ms 331680 KB Output is correct
41 Correct 406 ms 306680 KB Output is correct
42 Correct 449 ms 310904 KB Output is correct
43 Correct 760 ms 328900 KB Output is correct
44 Correct 763 ms 329428 KB Output is correct
45 Correct 490 ms 312124 KB Output is correct
46 Correct 466 ms 312192 KB Output is correct
47 Correct 777 ms 326648 KB Output is correct
48 Correct 665 ms 326776 KB Output is correct
49 Correct 210 ms 295532 KB Output is correct
50 Correct 206 ms 295572 KB Output is correct
51 Correct 212 ms 295288 KB Output is correct
52 Correct 207 ms 295160 KB Output is correct
53 Correct 205 ms 295664 KB Output is correct
54 Correct 231 ms 295544 KB Output is correct
55 Correct 236 ms 295420 KB Output is correct
56 Correct 232 ms 295416 KB Output is correct
57 Correct 258 ms 295544 KB Output is correct
58 Correct 218 ms 295160 KB Output is correct
59 Correct 235 ms 295288 KB Output is correct
60 Correct 208 ms 295160 KB Output is correct
61 Correct 1502 ms 362488 KB Output is correct
62 Correct 3504 ms 441380 KB Output is correct
63 Correct 3113 ms 442028 KB Output is correct
64 Correct 3368 ms 442144 KB Output is correct
65 Correct 984 ms 319516 KB Output is correct
66 Correct 1786 ms 341496 KB Output is correct
67 Correct 1901 ms 344440 KB Output is correct
68 Execution timed out 5121 ms 540904 KB Time limit exceeded
69 Halted 0 ms 0 KB -