oj.uz

Submission #274230

# Submission time Handle Problem Language Result Execution time Memory
274230 2020-08-19T10:08:43 Z ne4eHbKa Rectangles (IOI19_rect) C++17
100 / 100
 4785 ms 936304 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

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

void* MEM = malloc(800 << 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<short> l[N][N], u[N][N];
int p[N], length[N], la[N];
list<pii> fl[N], cl, fu, cu;
bool mk[N];
int c[2 * N], cn, xn, yn, rc[2 * N];
pii x[N], y[N];
int f[N], fn;

int fw[2 * N], fmax, nx[N + N], pr[N + N];
inline void finit(const int n) { fmax = n; memset(fw, 0, n + 1 << 2); }
inline void fadd(int i) { for(i = fmax - i; i <= fmax; i = nx[i]) fw[i]++; }
inline int fget(int i) { int v{}; for(i = fmax - i; i; i = pr[i]) v += fw[i]; return v; }

ll solve() {
    for(int i = 0; i < N + N; ++i) nx[i] = i + (i & -i), pr[i] = i - (i & -i);
    ll ans = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            swap(cl, fl[j]);
            auto it = cl.begin();
            for(const int &t : l[i][j]) {
                for(; it != cl.end() && it->ft < t; ++it);
                fl[j].push_back({t, 1 + (it != cl.end() && it->ft == t ? it->sd : 0)});
            }
            cl.clear();
            swap(cu, fu);
            it = cu.begin();
            for(const int &t : u[i][j]) {
                for(; it != cu.end() && it->ft < t; ++it);
                fu.push_back({t, 1 + (it != cu.end() && it->ft == t ? it->sd : 0)});
            }
            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;
            for(const auto &i : b) c[cn++] = i.sd;
            sort(c, c + cn);
            cn = unique(c, c + cn) - c;
            xn = yn = 0;
            finit(cn);
            for(int i = 0; i < cn; ++i) rc[c[i]] = i;
            for(const auto &i : a) x[xn++] = {i.sd, rc[i.ft]};
            for(const auto &i : b) y[yn++] = {i.ft, rc[i.sd]};
            sort(x, x + xn, [] (const pii &a, const pii &b) {return a.ft < b.ft;});
            for(int i = 0, it = 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);
        memset(mk, 0, m);
        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]];
            fn = 0;
            for(; t < m && a[i][p[t]] == v; ++t) {
                int j = p[t];
                mk[j] = true;
                length[j] = 1;
                f[fn++] = j;
                if(j + 1 < m && mk[j + 1]) unite(j, j + 1);
                if(j && mk[j - 1]) unite(j - 1, j);
            }
            for(int it = 0; it < fn; ++it) mk[f[it] = last(f[it])] = false;
            for(int it = 0; it < fn; ++it) {
                int j = f[it];
                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);
        memset(mk, 0, n);
        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];
            fn = 0;
            for(; t < n && a[p[t]][j] == v; ++t) {
                int i = p[t];
                mk[i] = true;
                length[i] = 1;
                f[fn++] = i;
                if(i + 1 < n && mk[i + 1]) unite(i, i + 1);
                if(i && mk[i - 1]) unite(i - 1, i);
            }
            for(int it = 0; it < fn; ++it) mk[f[it] = last(f[it])] = false;
            for(int it = 0; it < fn; ++it) {
                int i = f[it];
                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* operator new(size_t)':
rect.cpp:13:9: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
   13 |     MEM += f;
      |     ~~~~^~~~
rect.cpp: In function 'void S::finit(int)':
rect.cpp:43:60: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   43 | inline void finit(const int n) { fmax = n; memset(fw, 0, n + 1 << 2); }
      |                                                          ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 295160 KB Output is correct
2 Correct 193 ms 295416 KB Output is correct
3 Correct 195 ms 295288 KB Output is correct
4 Correct 199 ms 295288 KB Output is correct
5 Correct 217 ms 295160 KB Output is correct
6 Correct 199 ms 295176 KB Output is correct
7 Correct 194 ms 295288 KB Output is correct
8 Correct 216 ms 295160 KB Output is correct
9 Correct 197 ms 295180 KB Output is correct
10 Correct 213 ms 295164 KB Output is correct
11 Correct 196 ms 295260 KB Output is correct
12 Correct 201 ms 295192 KB Output is correct
13 Correct 232 ms 295160 KB Output is correct
14 Correct 197 ms 295160 KB Output is correct
15 Correct 207 ms 295160 KB Output is correct
16 Correct 201 ms 295068 KB Output is correct
17 Correct 205 ms 295160 KB Output is correct
18 Correct 211 ms 295156 KB Output is correct
19 Correct 196 ms 295176 KB Output is correct
20 Correct 191 ms 295180 KB Output is correct
21 Correct 197 ms 295160 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 295160 KB Output is correct
2 Correct 193 ms 295416 KB Output is correct
3 Correct 195 ms 295288 KB Output is correct
4 Correct 199 ms 295288 KB Output is correct
5 Correct 217 ms 295160 KB Output is correct
6 Correct 199 ms 295176 KB Output is correct
7 Correct 194 ms 295288 KB Output is correct
8 Correct 216 ms 295160 KB Output is correct
9 Correct 197 ms 295180 KB Output is correct
10 Correct 213 ms 295164 KB Output is correct
11 Correct 196 ms 295260 KB Output is correct
12 Correct 201 ms 295192 KB Output is correct
13 Correct 232 ms 295160 KB Output is correct
14 Correct 197 ms 295160 KB Output is correct
15 Correct 207 ms 295160 KB Output is correct
16 Correct 201 ms 295068 KB Output is correct
17 Correct 217 ms 295800 KB Output is correct
18 Correct 245 ms 295932 KB Output is correct
19 Correct 205 ms 295804 KB Output is correct
20 Correct 212 ms 295476 KB Output is correct
21 Correct 202 ms 295672 KB Output is correct
22 Correct 220 ms 295768 KB Output is correct
23 Correct 195 ms 295672 KB Output is correct
24 Correct 190 ms 295416 KB Output is correct
25 Correct 205 ms 295160 KB Output is correct
26 Correct 211 ms 295156 KB Output is correct
27 Correct 196 ms 295176 KB Output is correct
28 Correct 191 ms 295180 KB Output is correct
29 Correct 197 ms 295160 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 295160 KB Output is correct
2 Correct 193 ms 295416 KB Output is correct
3 Correct 195 ms 295288 KB Output is correct
4 Correct 199 ms 295288 KB Output is correct
5 Correct 217 ms 295160 KB Output is correct
6 Correct 199 ms 295176 KB Output is correct
7 Correct 194 ms 295288 KB Output is correct
8 Correct 216 ms 295160 KB Output is correct
9 Correct 197 ms 295180 KB Output is correct
10 Correct 213 ms 295164 KB Output is correct
11 Correct 196 ms 295260 KB Output is correct
12 Correct 201 ms 295192 KB Output is correct
13 Correct 232 ms 295160 KB Output is correct
14 Correct 197 ms 295160 KB Output is correct
15 Correct 207 ms 295160 KB Output is correct
16 Correct 201 ms 295068 KB Output is correct
17 Correct 217 ms 295800 KB Output is correct
18 Correct 245 ms 295932 KB Output is correct
19 Correct 205 ms 295804 KB Output is correct
20 Correct 212 ms 295476 KB Output is correct
21 Correct 202 ms 295672 KB Output is correct
22 Correct 220 ms 295768 KB Output is correct
23 Correct 195 ms 295672 KB Output is correct
24 Correct 190 ms 295416 KB Output is correct
25 Correct 204 ms 299140 KB Output is correct
26 Correct 205 ms 299128 KB Output is correct
27 Correct 202 ms 299256 KB Output is correct
28 Correct 209 ms 296852 KB Output is correct
29 Correct 202 ms 299000 KB Output is correct
30 Correct 208 ms 299000 KB Output is correct
31 Correct 203 ms 298872 KB Output is correct
32 Correct 216 ms 298748 KB Output is correct
33 Correct 205 ms 295160 KB Output is correct
34 Correct 211 ms 295156 KB Output is correct
35 Correct 196 ms 295176 KB Output is correct
36 Correct 191 ms 295180 KB Output is correct
37 Correct 197 ms 295160 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 295160 KB Output is correct
2 Correct 193 ms 295416 KB Output is correct
3 Correct 195 ms 295288 KB Output is correct
4 Correct 199 ms 295288 KB Output is correct
5 Correct 217 ms 295160 KB Output is correct
6 Correct 199 ms 295176 KB Output is correct
7 Correct 194 ms 295288 KB Output is correct
8 Correct 216 ms 295160 KB Output is correct
9 Correct 197 ms 295180 KB Output is correct
10 Correct 213 ms 295164 KB Output is correct
11 Correct 196 ms 295260 KB Output is correct
12 Correct 201 ms 295192 KB Output is correct
13 Correct 232 ms 295160 KB Output is correct
14 Correct 197 ms 295160 KB Output is correct
15 Correct 207 ms 295160 KB Output is correct
16 Correct 201 ms 295068 KB Output is correct
17 Correct 217 ms 295800 KB Output is correct
18 Correct 245 ms 295932 KB Output is correct
19 Correct 205 ms 295804 KB Output is correct
20 Correct 212 ms 295476 KB Output is correct
21 Correct 202 ms 295672 KB Output is correct
22 Correct 220 ms 295768 KB Output is correct
23 Correct 195 ms 295672 KB Output is correct
24 Correct 190 ms 295416 KB Output is correct
25 Correct 204 ms 299140 KB Output is correct
26 Correct 205 ms 299128 KB Output is correct
27 Correct 202 ms 299256 KB Output is correct
28 Correct 209 ms 296852 KB Output is correct
29 Correct 202 ms 299000 KB Output is correct
30 Correct 208 ms 299000 KB Output is correct
31 Correct 203 ms 298872 KB Output is correct
32 Correct 216 ms 298748 KB Output is correct
33 Correct 375 ms 322056 KB Output is correct
34 Correct 320 ms 322044 KB Output is correct
35 Correct 323 ms 321960 KB Output is correct
36 Correct 301 ms 321916 KB Output is correct
37 Correct 358 ms 344824 KB Output is correct
38 Correct 355 ms 344844 KB Output is correct
39 Correct 373 ms 344824 KB Output is correct
40 Correct 347 ms 341624 KB Output is correct
41 Correct 312 ms 310520 KB Output is correct
42 Correct 376 ms 316792 KB Output is correct
43 Correct 489 ms 343544 KB Output is correct
44 Correct 513 ms 344056 KB Output is correct
45 Correct 318 ms 319480 KB Output is correct
46 Correct 319 ms 319480 KB Output is correct
47 Correct 533 ms 340372 KB Output is correct
48 Correct 622 ms 340472 KB Output is correct
49 Correct 205 ms 295160 KB Output is correct
50 Correct 211 ms 295156 KB Output is correct
51 Correct 196 ms 295176 KB Output is correct
52 Correct 191 ms 295180 KB Output is correct
53 Correct 197 ms 295160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 295544 KB Output is correct
2 Correct 224 ms 295544 KB Output is correct
3 Correct 188 ms 295416 KB Output is correct
4 Correct 251 ms 295160 KB Output is correct
5 Correct 193 ms 295416 KB Output is correct
6 Correct 200 ms 295416 KB Output is correct
7 Correct 190 ms 295544 KB Output is correct
8 Correct 187 ms 295416 KB Output is correct
9 Correct 189 ms 295460 KB Output is correct
10 Correct 188 ms 295288 KB Output is correct
11 Correct 188 ms 295160 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 295160 KB Output is correct
2 Correct 982 ms 384712 KB Output is correct
3 Correct 2232 ms 489664 KB Output is correct
4 Correct 2121 ms 490628 KB Output is correct
5 Correct 1829 ms 490680 KB Output is correct
6 Correct 632 ms 319408 KB Output is correct
7 Correct 1198 ms 341240 KB Output is correct
8 Correct 1158 ms 344312 KB Output is correct
9 Correct 205 ms 295160 KB Output is correct
10 Correct 211 ms 295156 KB Output is correct
11 Correct 196 ms 295176 KB Output is correct
12 Correct 191 ms 295180 KB Output is correct
13 Correct 197 ms 295160 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 295160 KB Output is correct
2 Correct 193 ms 295416 KB Output is correct
3 Correct 195 ms 295288 KB Output is correct
4 Correct 199 ms 295288 KB Output is correct
5 Correct 217 ms 295160 KB Output is correct
6 Correct 199 ms 295176 KB Output is correct
7 Correct 194 ms 295288 KB Output is correct
8 Correct 216 ms 295160 KB Output is correct
9 Correct 197 ms 295180 KB Output is correct
10 Correct 213 ms 295164 KB Output is correct
11 Correct 196 ms 295260 KB Output is correct
12 Correct 201 ms 295192 KB Output is correct
13 Correct 232 ms 295160 KB Output is correct
14 Correct 197 ms 295160 KB Output is correct
15 Correct 207 ms 295160 KB Output is correct
16 Correct 201 ms 295068 KB Output is correct
17 Correct 217 ms 295800 KB Output is correct
18 Correct 245 ms 295932 KB Output is correct
19 Correct 205 ms 295804 KB Output is correct
20 Correct 212 ms 295476 KB Output is correct
21 Correct 202 ms 295672 KB Output is correct
22 Correct 220 ms 295768 KB Output is correct
23 Correct 195 ms 295672 KB Output is correct
24 Correct 190 ms 295416 KB Output is correct
25 Correct 204 ms 299140 KB Output is correct
26 Correct 205 ms 299128 KB Output is correct
27 Correct 202 ms 299256 KB Output is correct
28 Correct 209 ms 296852 KB Output is correct
29 Correct 202 ms 299000 KB Output is correct
30 Correct 208 ms 299000 KB Output is correct
31 Correct 203 ms 298872 KB Output is correct
32 Correct 216 ms 298748 KB Output is correct
33 Correct 375 ms 322056 KB Output is correct
34 Correct 320 ms 322044 KB Output is correct
35 Correct 323 ms 321960 KB Output is correct
36 Correct 301 ms 321916 KB Output is correct
37 Correct 358 ms 344824 KB Output is correct
38 Correct 355 ms 344844 KB Output is correct
39 Correct 373 ms 344824 KB Output is correct
40 Correct 347 ms 341624 KB Output is correct
41 Correct 312 ms 310520 KB Output is correct
42 Correct 376 ms 316792 KB Output is correct
43 Correct 489 ms 343544 KB Output is correct
44 Correct 513 ms 344056 KB Output is correct
45 Correct 318 ms 319480 KB Output is correct
46 Correct 319 ms 319480 KB Output is correct
47 Correct 533 ms 340372 KB Output is correct
48 Correct 622 ms 340472 KB Output is correct
49 Correct 239 ms 295544 KB Output is correct
50 Correct 224 ms 295544 KB Output is correct
51 Correct 188 ms 295416 KB Output is correct
52 Correct 251 ms 295160 KB Output is correct
53 Correct 193 ms 295416 KB Output is correct
54 Correct 200 ms 295416 KB Output is correct
55 Correct 190 ms 295544 KB Output is correct
56 Correct 187 ms 295416 KB Output is correct
57 Correct 189 ms 295460 KB Output is correct
58 Correct 188 ms 295288 KB Output is correct
59 Correct 188 ms 295160 KB Output is correct
60 Correct 186 ms 295160 KB Output is correct
61 Correct 982 ms 384712 KB Output is correct
62 Correct 2232 ms 489664 KB Output is correct
63 Correct 2121 ms 490628 KB Output is correct
64 Correct 1829 ms 490680 KB Output is correct
65 Correct 632 ms 319408 KB Output is correct
66 Correct 1198 ms 341240 KB Output is correct
67 Correct 1158 ms 344312 KB Output is correct
68 Correct 2556 ms 637592 KB Output is correct
69 Correct 2478 ms 639156 KB Output is correct
70 Correct 2782 ms 639608 KB Output is correct
71 Correct 2298 ms 639900 KB Output is correct
72 Correct 4461 ms 932188 KB Output is correct
73 Correct 4051 ms 682328 KB Output is correct
74 Correct 3581 ms 695932 KB Output is correct
75 Correct 4785 ms 921596 KB Output is correct
76 Correct 2993 ms 702380 KB Output is correct
77 Correct 3783 ms 818296 KB Output is correct
78 Correct 4767 ms 932456 KB Output is correct
79 Correct 2605 ms 649272 KB Output is correct
80 Correct 4497 ms 891680 KB Output is correct
81 Correct 4344 ms 873348 KB Output is correct
82 Correct 2442 ms 705264 KB Output is correct
83 Correct 4331 ms 935492 KB Output is correct
84 Correct 4362 ms 936168 KB Output is correct
85 Correct 4364 ms 936304 KB Output is correct
86 Correct 205 ms 295160 KB Output is correct
87 Correct 211 ms 295156 KB Output is correct
88 Correct 196 ms 295176 KB Output is correct
89 Correct 191 ms 295180 KB Output is correct
90 Correct 197 ms 295160 KB Output is correct