oj.uz

Submission #208235

# Submission time Handle Problem Language Result Execution time Memory
208235 2020-03-10T11:39:08 Z balbit Rectangles (IOI19_rect) C++14
100 / 100
 4202 ms 1029064 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"-1\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b) % mo;
}

const int MX = 2505;

vector<pii> hof[MX][MX], cof[MX][MX];
#define REP(i,n) for (int i = 0; i<n; ++i)
#define FOR(i,a,b) for (int i = a; i<b; ++i)

vector<int> g[MX][MX];

int s1[MX*2], s2[MX*2];
int sit = 0;

void go(vector<pii> up[MX][MX], vector<vector<int> > a) {
    clock_t t2 = clock();
    int n = a.size(), m = a[0].size();
    REP(i,m) REP(j,m) g[i][j] . clear();
    REP(i,n) {
        vector<int> &b = a[i];
        sit = 0;
        s1[sit] = b[0]; s2[sit] = 0; ++ sit;
        FOR(j,1,m) {
            while (sit && s1[sit-1] < b[j]) {
                g[s2[--sit]][j].pb(i);
            }
            if (sit) {
                g[s2[sit-1]][j].pb(i);
            }
            while (sit && s1[sit-1] == b[j]) --sit;
            s1[sit] = b[j];
            s2[sit] = j;
            ++sit;
        }
    }
    bug((clock() - t2) / (double) CLOCKS_PER_SEC);
    t2 = clock();
    REP(i,m-1) FOR(j,i+2,m) {
        if (SZ(g[i][j]) == 0) continue;
        int first = 0;
        int sg = SZ(g[i][j]);
        FOR(it,1, sg + 1) {
            if ( g[i][j][it] != g[i][j][it-1]+1 ) {
                FOR(nat, first, it) if (g[i][j][nat] -1 >= 0) up[g[i][j][nat]-1][i].push_back({g[i][j][it-1]+1,j});
                first = it;
            }
        }
        FOR(nat, first, sg ) if (g[i][j][nat] -1 >= 0) up[g[i][j][nat]-1][i].push_back({g[i][j][sg -1]+1,j});
//                first = it;
    }
    bug((clock() - t2) / (double) CLOCKS_PER_SEC);
}

void go2(vector<pii> up[MX][MX], vector<vector<int> > a) {
    clock_t t2 = clock();
    int n = a.size(), m = a[0].size();
    REP(i,m) REP(j,m) g[i][j] . clear();
    REP(i,n) {
        vector<int> &b = a[i];
        sit = 0;
        s1[sit] = b[0]; s2[sit] = 0; ++ sit;
        FOR(j,1,m) {
            while (sit && s1[sit-1] < b[j]) {
                g[s2[--sit]][j].pb(i);
            }
            if (sit) {
                g[s2[sit-1]][j].pb(i);
            }
            while (sit && s1[sit-1] == b[j]) --sit;
            s1[sit] = b[j];
            s2[sit] = j;
            ++sit;
        }
    }
    bug((clock() - t2) / (double) CLOCKS_PER_SEC);
    t2 = clock();
    int cnt = 0;
    REP(i,m-1) FOR(j,i+2,m) {
        if (SZ(g[i][j]) == 0) continue;
        int first = 0;
        int sg = SZ(g[i][j]);
        FOR(it,1, sg + 1) {
            if ( g[i][j][it] != g[i][j][it-1]+1 ) {
                FOR(nat, first, it) if (g[i][j][nat] -1 >= 0) up[i][g[i][j][nat]-1].push_back({j,g[i][j][it-1]+1}), cnt++;
                first = it;
            }
        }
        FOR(nat, first, sg ) if (g[i][j][nat] -1 >= 0) up[i][g[i][j][nat]-1].push_back({j,g[i][j][sg -1]+1}), cnt++;
//                first = it;
    }
    bug(cnt);
    bug((clock() - t2) / (double) CLOCKS_PER_SEC);
}

int s[MX];
int QU(int e) {
    int re = 0;
    for (e++; e>0; e-=e&-e) re += s[e];
    return re;
}
void MO(int e, int v) {
    for (e++; e<MX; e+=e&-e) s[e] += v;
}

ll count_rectangles(vector<vector<int> > a){
    clock_t tt = clock();
    go(hof,a);
    int n = a.size(), m = a[0].size();
//#ifdef BALBIT
//    REP(i,n) REP(j,m) {
//        if (SZ(hof[i][j]) == 0) continue;
//        bug(i,j);
//        for (pii x : hof[i][j]) {
//            cerr<<x.f<<' '<<x.s<<"\n";
//        }
//        cerr<<endl;
//    }
//#endif
    vector<vector<int> > aT(m);
    REP(j,m) {
        REP(i,n) {
            aT[j].pb(a[i][j]);
        }
    }
    go2(cof, aT);
//#ifdef BALBIT
//    REP(i,n) REP(j,m) {
//        if (SZ(cof[i][j]) == 0) continue;
//        bug(i,j, j,i);
//        for (pii x : cof[j][i]) {
//            cerr<<x.f<<' '<<x.s<<"\n";
//        }
//        cerr<<endl;
//    }
//#endif
    bug((clock() - tt) / (double) CLOCKS_PER_SEC);
    tt = clock();
    ll re = 0;
    REP(i,n-2) REP(j,m-2) {
        if (hof[i][j].size() == 0 || cof[i][j].size() == 0) continue;
        vector<pii> &ud = hof[i][j], &lr = cof[i][j];
        sort(ALL(ud), greater<pii> ());
        sort(ALL(lr), greater<pii> ());
        int it = 0;
        for (pii & q : lr) {
            while (it < SZ(ud) && ud[it].f >= q.f) {
                MO(ud[it].s,1);
                ++it;
            }
            re += QU(q.s);
//            bug(q.s,it,QU(q.s));
        }
        REP(jt, it) {
            MO(ud[jt].s,-1);
        }
    }
    bug((clock() - tt) / (double) CLOCKS_PER_SEC);
    return re;
}

#ifdef BALBIT
signed main(){
    IOS();
//    ll lol = count_rectangles({{0,5,5,0},{5,2,2,5},{5,3,4,5}});
//    bug(lol);
//    ll lol = count_rectangles({{4, 8, 7, 5, 6},
//{7, 4, 10, 3, 5},
//{9, 7, 20, 14, 2},
//{9, 14, 7, 3, 6},
//{5, 7, 5, 2, 7},
//{4, 5, 13, 5, 6}});
//    bug(lol);
//    ll lol = count_rectangles({{0,5,5,0},{5,1,2,5},{5,3,4,5},{0,5,5,0}});
    int N = 2500, M = 2500;
    vector<vector<int> > a(N);
    REP(i,N) REP(j,M){
        a[i].pb(rand() % 10000000);
    }
    bug("GO");
    ll lol = count_rectangles(a);
    bug(lol);
}
#endif

Compilation message

rect.cpp: In function 'void go(std::vector<std::pair<int, int> > (*)[2505], std::vector<std::vector<int> >)':
rect.cpp:61:13: warning: variable 't2' set but not used [-Wunused-but-set-variable]
     clock_t t2 = clock();
             ^~
rect.cpp: In function 'void go2(std::vector<std::pair<int, int> > (*)[2505], std::vector<std::vector<int> >)':
rect.cpp:100:13: warning: variable 't2' set but not used [-Wunused-but-set-variable]
     clock_t t2 = clock();
             ^~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:151:13: warning: variable 'tt' set but not used [-Wunused-but-set-variable]
     clock_t tt = clock();
             ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 442488 KB Output is correct
2 Correct 260 ms 442744 KB Output is correct
3 Correct 250 ms 442488 KB Output is correct
4 Correct 257 ms 442488 KB Output is correct
5 Correct 260 ms 442424 KB Output is correct
6 Correct 262 ms 442488 KB Output is correct
7 Correct 262 ms 442488 KB Output is correct
8 Correct 265 ms 442464 KB Output is correct
9 Correct 261 ms 442488 KB Output is correct
10 Correct 263 ms 442488 KB Output is correct
11 Correct 262 ms 442488 KB Output is correct
12 Correct 260 ms 442488 KB Output is correct
13 Correct 263 ms 442488 KB Output is correct
14 Correct 256 ms 442360 KB Output is correct
15 Correct 298 ms 442360 KB Output is correct
16 Correct 262 ms 442360 KB Output is correct
17 Correct 252 ms 442360 KB Output is correct
18 Correct 258 ms 442360 KB Output is correct
19 Correct 257 ms 442488 KB Output is correct
20 Correct 269 ms 442360 KB Output is correct
21 Correct 260 ms 442360 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 442488 KB Output is correct
2 Correct 260 ms 442744 KB Output is correct
3 Correct 250 ms 442488 KB Output is correct
4 Correct 257 ms 442488 KB Output is correct
5 Correct 260 ms 442424 KB Output is correct
6 Correct 262 ms 442488 KB Output is correct
7 Correct 262 ms 442488 KB Output is correct
8 Correct 265 ms 442464 KB Output is correct
9 Correct 261 ms 442488 KB Output is correct
10 Correct 263 ms 442488 KB Output is correct
11 Correct 262 ms 442488 KB Output is correct
12 Correct 260 ms 442488 KB Output is correct
13 Correct 263 ms 442488 KB Output is correct
14 Correct 256 ms 442360 KB Output is correct
15 Correct 298 ms 442360 KB Output is correct
16 Correct 262 ms 442360 KB Output is correct
17 Correct 254 ms 443000 KB Output is correct
18 Correct 266 ms 443128 KB Output is correct
19 Correct 263 ms 443016 KB Output is correct
20 Correct 261 ms 442744 KB Output is correct
21 Correct 259 ms 442872 KB Output is correct
22 Correct 263 ms 442872 KB Output is correct
23 Correct 262 ms 442872 KB Output is correct
24 Correct 260 ms 442616 KB Output is correct
25 Correct 252 ms 442360 KB Output is correct
26 Correct 258 ms 442360 KB Output is correct
27 Correct 257 ms 442488 KB Output is correct
28 Correct 269 ms 442360 KB Output is correct
29 Correct 260 ms 442360 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 442488 KB Output is correct
2 Correct 260 ms 442744 KB Output is correct
3 Correct 250 ms 442488 KB Output is correct
4 Correct 257 ms 442488 KB Output is correct
5 Correct 260 ms 442424 KB Output is correct
6 Correct 262 ms 442488 KB Output is correct
7 Correct 262 ms 442488 KB Output is correct
8 Correct 265 ms 442464 KB Output is correct
9 Correct 261 ms 442488 KB Output is correct
10 Correct 263 ms 442488 KB Output is correct
11 Correct 262 ms 442488 KB Output is correct
12 Correct 260 ms 442488 KB Output is correct
13 Correct 263 ms 442488 KB Output is correct
14 Correct 256 ms 442360 KB Output is correct
15 Correct 298 ms 442360 KB Output is correct
16 Correct 262 ms 442360 KB Output is correct
17 Correct 254 ms 443000 KB Output is correct
18 Correct 266 ms 443128 KB Output is correct
19 Correct 263 ms 443016 KB Output is correct
20 Correct 261 ms 442744 KB Output is correct
21 Correct 259 ms 442872 KB Output is correct
22 Correct 263 ms 442872 KB Output is correct
23 Correct 262 ms 442872 KB Output is correct
24 Correct 260 ms 442616 KB Output is correct
25 Correct 291 ms 446200 KB Output is correct
26 Correct 274 ms 446200 KB Output is correct
27 Correct 271 ms 446200 KB Output is correct
28 Correct 265 ms 444408 KB Output is correct
29 Correct 273 ms 445304 KB Output is correct
30 Correct 285 ms 445432 KB Output is correct
31 Correct 272 ms 445304 KB Output is correct
32 Correct 279 ms 445304 KB Output is correct
33 Correct 252 ms 442360 KB Output is correct
34 Correct 258 ms 442360 KB Output is correct
35 Correct 257 ms 442488 KB Output is correct
36 Correct 269 ms 442360 KB Output is correct
37 Correct 260 ms 442360 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 442488 KB Output is correct
2 Correct 260 ms 442744 KB Output is correct
3 Correct 250 ms 442488 KB Output is correct
4 Correct 257 ms 442488 KB Output is correct
5 Correct 260 ms 442424 KB Output is correct
6 Correct 262 ms 442488 KB Output is correct
7 Correct 262 ms 442488 KB Output is correct
8 Correct 265 ms 442464 KB Output is correct
9 Correct 261 ms 442488 KB Output is correct
10 Correct 263 ms 442488 KB Output is correct
11 Correct 262 ms 442488 KB Output is correct
12 Correct 260 ms 442488 KB Output is correct
13 Correct 263 ms 442488 KB Output is correct
14 Correct 256 ms 442360 KB Output is correct
15 Correct 298 ms 442360 KB Output is correct
16 Correct 262 ms 442360 KB Output is correct
17 Correct 254 ms 443000 KB Output is correct
18 Correct 266 ms 443128 KB Output is correct
19 Correct 263 ms 443016 KB Output is correct
20 Correct 261 ms 442744 KB Output is correct
21 Correct 259 ms 442872 KB Output is correct
22 Correct 263 ms 442872 KB Output is correct
23 Correct 262 ms 442872 KB Output is correct
24 Correct 260 ms 442616 KB Output is correct
25 Correct 291 ms 446200 KB Output is correct
26 Correct 274 ms 446200 KB Output is correct
27 Correct 271 ms 446200 KB Output is correct
28 Correct 265 ms 444408 KB Output is correct
29 Correct 273 ms 445304 KB Output is correct
30 Correct 285 ms 445432 KB Output is correct
31 Correct 272 ms 445304 KB Output is correct
32 Correct 279 ms 445304 KB Output is correct
33 Correct 419 ms 479864 KB Output is correct
34 Correct 394 ms 475128 KB Output is correct
35 Correct 408 ms 475128 KB Output is correct
36 Correct 371 ms 470400 KB Output is correct
37 Correct 469 ms 490512 KB Output is correct
38 Correct 463 ms 493320 KB Output is correct
39 Correct 457 ms 490720 KB Output is correct
40 Correct 435 ms 490872 KB Output is correct
41 Correct 358 ms 463356 KB Output is correct
42 Correct 384 ms 466552 KB Output is correct
43 Correct 495 ms 477432 KB Output is correct
44 Correct 506 ms 479608 KB Output is correct
45 Correct 367 ms 462328 KB Output is correct
46 Correct 367 ms 462456 KB Output is correct
47 Correct 474 ms 476640 KB Output is correct
48 Correct 470 ms 477724 KB Output is correct
49 Correct 252 ms 442360 KB Output is correct
50 Correct 258 ms 442360 KB Output is correct
51 Correct 257 ms 442488 KB Output is correct
52 Correct 269 ms 442360 KB Output is correct
53 Correct 260 ms 442360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 443344 KB Output is correct
2 Correct 284 ms 443128 KB Output is correct
3 Correct 282 ms 442872 KB Output is correct
4 Correct 261 ms 442360 KB Output is correct
5 Correct 292 ms 443256 KB Output is correct
6 Correct 286 ms 443360 KB Output is correct
7 Correct 286 ms 443128 KB Output is correct
8 Correct 295 ms 443156 KB Output is correct
9 Correct 282 ms 443128 KB Output is correct
10 Correct 285 ms 442872 KB Output is correct
11 Correct 295 ms 443256 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 442360 KB Output is correct
2 Correct 1052 ms 579280 KB Output is correct
3 Correct 2001 ms 710804 KB Output is correct
4 Correct 2009 ms 711992 KB Output is correct
5 Correct 2020 ms 711688 KB Output is correct
6 Correct 718 ms 533592 KB Output is correct
7 Correct 1162 ms 595832 KB Output is correct
8 Correct 1221 ms 603644 KB Output is correct
9 Correct 252 ms 442360 KB Output is correct
10 Correct 258 ms 442360 KB Output is correct
11 Correct 257 ms 442488 KB Output is correct
12 Correct 269 ms 442360 KB Output is correct
13 Correct 260 ms 442360 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 442488 KB Output is correct
2 Correct 260 ms 442744 KB Output is correct
3 Correct 250 ms 442488 KB Output is correct
4 Correct 257 ms 442488 KB Output is correct
5 Correct 260 ms 442424 KB Output is correct
6 Correct 262 ms 442488 KB Output is correct
7 Correct 262 ms 442488 KB Output is correct
8 Correct 265 ms 442464 KB Output is correct
9 Correct 261 ms 442488 KB Output is correct
10 Correct 263 ms 442488 KB Output is correct
11 Correct 262 ms 442488 KB Output is correct
12 Correct 260 ms 442488 KB Output is correct
13 Correct 263 ms 442488 KB Output is correct
14 Correct 256 ms 442360 KB Output is correct
15 Correct 298 ms 442360 KB Output is correct
16 Correct 262 ms 442360 KB Output is correct
17 Correct 254 ms 443000 KB Output is correct
18 Correct 266 ms 443128 KB Output is correct
19 Correct 263 ms 443016 KB Output is correct
20 Correct 261 ms 442744 KB Output is correct
21 Correct 259 ms 442872 KB Output is correct
22 Correct 263 ms 442872 KB Output is correct
23 Correct 262 ms 442872 KB Output is correct
24 Correct 260 ms 442616 KB Output is correct
25 Correct 291 ms 446200 KB Output is correct
26 Correct 274 ms 446200 KB Output is correct
27 Correct 271 ms 446200 KB Output is correct
28 Correct 265 ms 444408 KB Output is correct
29 Correct 273 ms 445304 KB Output is correct
30 Correct 285 ms 445432 KB Output is correct
31 Correct 272 ms 445304 KB Output is correct
32 Correct 279 ms 445304 KB Output is correct
33 Correct 419 ms 479864 KB Output is correct
34 Correct 394 ms 475128 KB Output is correct
35 Correct 408 ms 475128 KB Output is correct
36 Correct 371 ms 470400 KB Output is correct
37 Correct 469 ms 490512 KB Output is correct
38 Correct 463 ms 493320 KB Output is correct
39 Correct 457 ms 490720 KB Output is correct
40 Correct 435 ms 490872 KB Output is correct
41 Correct 358 ms 463356 KB Output is correct
42 Correct 384 ms 466552 KB Output is correct
43 Correct 495 ms 477432 KB Output is correct
44 Correct 506 ms 479608 KB Output is correct
45 Correct 367 ms 462328 KB Output is correct
46 Correct 367 ms 462456 KB Output is correct
47 Correct 474 ms 476640 KB Output is correct
48 Correct 470 ms 477724 KB Output is correct
49 Correct 288 ms 443344 KB Output is correct
50 Correct 284 ms 443128 KB Output is correct
51 Correct 282 ms 442872 KB Output is correct
52 Correct 261 ms 442360 KB Output is correct
53 Correct 292 ms 443256 KB Output is correct
54 Correct 286 ms 443360 KB Output is correct
55 Correct 286 ms 443128 KB Output is correct
56 Correct 295 ms 443156 KB Output is correct
57 Correct 282 ms 443128 KB Output is correct
58 Correct 285 ms 442872 KB Output is correct
59 Correct 295 ms 443256 KB Output is correct
60 Correct 261 ms 442360 KB Output is correct
61 Correct 1052 ms 579280 KB Output is correct
62 Correct 2001 ms 710804 KB Output is correct
63 Correct 2009 ms 711992 KB Output is correct
64 Correct 2020 ms 711688 KB Output is correct
65 Correct 718 ms 533592 KB Output is correct
66 Correct 1162 ms 595832 KB Output is correct
67 Correct 1221 ms 603644 KB Output is correct
68 Correct 3423 ms 894716 KB Output is correct
69 Correct 2337 ms 827032 KB Output is correct
70 Correct 3027 ms 827388 KB Output is correct
71 Correct 1950 ms 760248 KB Output is correct
72 Correct 4140 ms 1029064 KB Output is correct
73 Correct 2495 ms 722324 KB Output is correct
74 Correct 2628 ms 730740 KB Output is correct
75 Correct 3843 ms 867632 KB Output is correct
76 Correct 2679 ms 720032 KB Output is correct
77 Correct 3253 ms 804792 KB Output is correct
78 Correct 3937 ms 872148 KB Output is correct
79 Correct 2238 ms 699268 KB Output is correct
80 Correct 3676 ms 852344 KB Output is correct
81 Correct 3540 ms 842300 KB Output is correct
82 Correct 2612 ms 825468 KB Output is correct
83 Correct 4202 ms 1023712 KB Output is correct
84 Correct 4141 ms 1023780 KB Output is correct
85 Correct 4155 ms 1023676 KB Output is correct
86 Correct 252 ms 442360 KB Output is correct
87 Correct 258 ms 442360 KB Output is correct
88 Correct 257 ms 442488 KB Output is correct
89 Correct 269 ms 442360 KB Output is correct
90 Correct 260 ms 442360 KB Output is correct