oj.uz

Submission #154449

# Submission time Handle Problem Language Result Execution time Memory
154449 2019-09-21T22:32:38 Z crackersamdjam Rectangles (IOI19_rect) C++14
72 / 100
 2929 ms 1048580 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4,popcnt,abm,mmx,tune=native")

#include <bits/stdc++.h>
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}

const int MM = 2502;

int n, m, ans, stl, vecl;
int first[MM], last[MM], bit[MM];
std::pair<int, int> st[MM], vec[MM];
std::map<int, int, std::greater<int>> hor[MM][MM], vert[MM][MM];

inline void update(int i, int v){
    for(; i < MM; i += i&-i)
        bit[i] += v;
}

inline int query(int i){
    int ret = 0;
    for(; i; i -= i&-i)
        ret += bit[i];
    return ret;
}

long long count_rectangles(std::vector<std::vector<int>> a){
    n = a.size(), m = a[0].size();
    
    for(int i = 0; i < n; i++){
        stl = 0;
        for(int j = 0; j < m; j++){
            //remove duplicates
            while(stl && st[stl].first < a[i][j])
                stl--;
            first[j] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
            st[++stl] = {a[i][j], j};
        }
        stl = 0;
        for(int j = m-1; j >= 0; j--){
            while(stl && st[stl].first <= a[i][j])
                stl--;
            last[j] = !stl ? -1 : st[stl].second;
            st[++stl] = {a[i][j], j};
        }
        for(int j = 0; j < m; j++){
            if(first[j] == -1 || last[j] == -1)
                continue;
            
            first[j]++, last[j]--;
            
            hor[i][first[j]][last[j]] = 1;
        }
    }
    
    for(int j = 0; j < m; j++){
        stl = 0;
        for(int i = 0; i < n; i++){
            //remove duplicates
            while(stl && st[stl].first < a[i][j])
                stl--;
            first[i] = (!stl || st[stl].first == a[i][j]) ? -1 : st[stl].second;
            st[++stl] = {a[i][j], i};
        }
        stl = 0;
        for(int i = n-1; i >= 0; i--){
            while(stl && st[stl].first <= a[i][j])
                stl--;
            last[i] = !stl ? -1 : st[stl].second;
            st[++stl] = {a[i][j], i};
        }
        for(int i = 0; i < n; i++){
            if(first[i] == -1 || last[i] == -1)
                continue;
            
            first[i]++, last[i]--;
            
            vert[first[i]][j][last[i]] = 1;
        }
    }
    
    for(int i = n-1; i >= 0; i--){
        for(int j = m-1; j >= 0; j--){
            for(auto &x: hor[i][j])
                if(hor[i+1][j].count(x.first))
                    x.second += hor[i+1][j][x.first];
            
            for(auto &x: vert[i][j])
                if(vert[i][j+1].count(x.first))
                    x.second += vert[i][j+1][x.first];
            
            for(auto &x: hor[i][j])
                vec[vecl++] = {x.first-j+1, x.second};
            sort(vec, vec+vecl, [](auto &x, auto &y){
                return x.second > y.second;
            });
            
            int l = 0;
            
            for(auto &b: vert[i][j]){
                int bf = b.first-i+1;
                
                while(l < vecl && bf <= vec[l].second)
                    update(vec[l++].first, 1);
                ans += query(b.second);
            }
            
            while(l)
                update(vec[--l].first, -1);
            
            vecl = 0;
        }
    }
    
    return ans;
}


/*
 * in a row, for every point, get 1st left > and 1st right greater
 * this will get all possible
 *
 * using mono stack
 *
 *
 * sort row segments
 * starting at point i, on row j
 * for each (i, r), dp for how long can go down
 *
 * then do same for vertical
 *
 * when it works is when: vert_seg <= dp_vert[hor_seg] and hor_seg <= dp_hor[vert_seg]
 *
 * sort hor and vert by y reversed
 * loop through vert with l ptr for hor
 *      while hor[l] >= y, push hor[l++].x into bit
 *      answer += query_greater_than_equals(vert[i].x)
 *
 * vertical <= NM
 * horizontal <= NM
 * time complexity vert * log(hor) = NM log(NM)
 */

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 588408 KB Output is correct
2 Correct 537 ms 588520 KB Output is correct
3 Correct 533 ms 588516 KB Output is correct
4 Correct 536 ms 588564 KB Output is correct
5 Correct 533 ms 588344 KB Output is correct
6 Correct 538 ms 588472 KB Output is correct
7 Correct 537 ms 588408 KB Output is correct
8 Correct 534 ms 588452 KB Output is correct
9 Correct 575 ms 588432 KB Output is correct
10 Correct 537 ms 588580 KB Output is correct
11 Correct 537 ms 588560 KB Output is correct
12 Correct 537 ms 588408 KB Output is correct
13 Correct 529 ms 588448 KB Output is correct
14 Correct 565 ms 588412 KB Output is correct
15 Correct 533 ms 588408 KB Output is correct
16 Correct 545 ms 588372 KB Output is correct
17 Correct 611 ms 588408 KB Output is correct
18 Correct 559 ms 588424 KB Output is correct
19 Correct 578 ms 588424 KB Output is correct
20 Correct 533 ms 588408 KB Output is correct
21 Correct 534 ms 588360 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 588408 KB Output is correct
2 Correct 537 ms 588520 KB Output is correct
3 Correct 533 ms 588516 KB Output is correct
4 Correct 536 ms 588564 KB Output is correct
5 Correct 533 ms 588344 KB Output is correct
6 Correct 538 ms 588472 KB Output is correct
7 Correct 537 ms 588408 KB Output is correct
8 Correct 534 ms 588452 KB Output is correct
9 Correct 575 ms 588432 KB Output is correct
10 Correct 537 ms 588580 KB Output is correct
11 Correct 537 ms 588560 KB Output is correct
12 Correct 537 ms 588408 KB Output is correct
13 Correct 529 ms 588448 KB Output is correct
14 Correct 565 ms 588412 KB Output is correct
15 Correct 533 ms 588408 KB Output is correct
16 Correct 545 ms 588372 KB Output is correct
17 Correct 568 ms 589064 KB Output is correct
18 Correct 535 ms 589020 KB Output is correct
19 Correct 537 ms 589048 KB Output is correct
20 Correct 536 ms 588680 KB Output is correct
21 Correct 537 ms 589128 KB Output is correct
22 Correct 558 ms 589040 KB Output is correct
23 Correct 533 ms 589048 KB Output is correct
24 Correct 565 ms 588792 KB Output is correct
25 Correct 611 ms 588408 KB Output is correct
26 Correct 559 ms 588424 KB Output is correct
27 Correct 578 ms 588424 KB Output is correct
28 Correct 533 ms 588408 KB Output is correct
29 Correct 534 ms 588360 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 588408 KB Output is correct
2 Correct 537 ms 588520 KB Output is correct
3 Correct 533 ms 588516 KB Output is correct
4 Correct 536 ms 588564 KB Output is correct
5 Correct 533 ms 588344 KB Output is correct
6 Correct 538 ms 588472 KB Output is correct
7 Correct 537 ms 588408 KB Output is correct
8 Correct 534 ms 588452 KB Output is correct
9 Correct 575 ms 588432 KB Output is correct
10 Correct 537 ms 588580 KB Output is correct
11 Correct 537 ms 588560 KB Output is correct
12 Correct 537 ms 588408 KB Output is correct
13 Correct 529 ms 588448 KB Output is correct
14 Correct 565 ms 588412 KB Output is correct
15 Correct 533 ms 588408 KB Output is correct
16 Correct 545 ms 588372 KB Output is correct
17 Correct 568 ms 589064 KB Output is correct
18 Correct 535 ms 589020 KB Output is correct
19 Correct 537 ms 589048 KB Output is correct
20 Correct 536 ms 588680 KB Output is correct
21 Correct 537 ms 589128 KB Output is correct
22 Correct 558 ms 589040 KB Output is correct
23 Correct 533 ms 589048 KB Output is correct
24 Correct 565 ms 588792 KB Output is correct
25 Correct 576 ms 592744 KB Output is correct
26 Correct 555 ms 592848 KB Output is correct
27 Correct 553 ms 592700 KB Output is correct
28 Correct 551 ms 590140 KB Output is correct
29 Correct 559 ms 592400 KB Output is correct
30 Correct 553 ms 592580 KB Output is correct
31 Correct 555 ms 592352 KB Output is correct
32 Correct 569 ms 592244 KB Output is correct
33 Correct 611 ms 588408 KB Output is correct
34 Correct 559 ms 588424 KB Output is correct
35 Correct 578 ms 588424 KB Output is correct
36 Correct 533 ms 588408 KB Output is correct
37 Correct 534 ms 588360 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 588408 KB Output is correct
2 Correct 537 ms 588520 KB Output is correct
3 Correct 533 ms 588516 KB Output is correct
4 Correct 536 ms 588564 KB Output is correct
5 Correct 533 ms 588344 KB Output is correct
6 Correct 538 ms 588472 KB Output is correct
7 Correct 537 ms 588408 KB Output is correct
8 Correct 534 ms 588452 KB Output is correct
9 Correct 575 ms 588432 KB Output is correct
10 Correct 537 ms 588580 KB Output is correct
11 Correct 537 ms 588560 KB Output is correct
12 Correct 537 ms 588408 KB Output is correct
13 Correct 529 ms 588448 KB Output is correct
14 Correct 565 ms 588412 KB Output is correct
15 Correct 533 ms 588408 KB Output is correct
16 Correct 545 ms 588372 KB Output is correct
17 Correct 568 ms 589064 KB Output is correct
18 Correct 535 ms 589020 KB Output is correct
19 Correct 537 ms 589048 KB Output is correct
20 Correct 536 ms 588680 KB Output is correct
21 Correct 537 ms 589128 KB Output is correct
22 Correct 558 ms 589040 KB Output is correct
23 Correct 533 ms 589048 KB Output is correct
24 Correct 565 ms 588792 KB Output is correct
25 Correct 576 ms 592744 KB Output is correct
26 Correct 555 ms 592848 KB Output is correct
27 Correct 553 ms 592700 KB Output is correct
28 Correct 551 ms 590140 KB Output is correct
29 Correct 559 ms 592400 KB Output is correct
30 Correct 553 ms 592580 KB Output is correct
31 Correct 555 ms 592352 KB Output is correct
32 Correct 569 ms 592244 KB Output is correct
33 Correct 659 ms 616956 KB Output is correct
34 Correct 701 ms 617092 KB Output is correct
35 Correct 629 ms 616952 KB Output is correct
36 Correct 686 ms 617076 KB Output is correct
37 Correct 748 ms 639992 KB Output is correct
38 Correct 748 ms 639776 KB Output is correct
39 Correct 736 ms 640008 KB Output is correct
40 Correct 787 ms 636676 KB Output is correct
41 Correct 691 ms 604736 KB Output is correct
42 Correct 709 ms 611216 KB Output is correct
43 Correct 874 ms 638060 KB Output is correct
44 Correct 853 ms 639468 KB Output is correct
45 Correct 680 ms 613860 KB Output is correct
46 Correct 676 ms 613916 KB Output is correct
47 Correct 801 ms 635640 KB Output is correct
48 Correct 817 ms 635820 KB Output is correct
49 Correct 611 ms 588408 KB Output is correct
50 Correct 559 ms 588424 KB Output is correct
51 Correct 578 ms 588424 KB Output is correct
52 Correct 533 ms 588408 KB Output is correct
53 Correct 534 ms 588360 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 589144 KB Output is correct
2 Correct 538 ms 588896 KB Output is correct
3 Correct 532 ms 588436 KB Output is correct
4 Correct 532 ms 588340 KB Output is correct
5 Correct 538 ms 588868 KB Output is correct
6 Correct 535 ms 588992 KB Output is correct
7 Correct 539 ms 588948 KB Output is correct
8 Correct 546 ms 588852 KB Output is correct
9 Correct 554 ms 588800 KB Output is correct
10 Correct 615 ms 588408 KB Output is correct
11 Correct 536 ms 588676 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 588304 KB Output is correct
2 Correct 1217 ms 680252 KB Output is correct
3 Correct 2087 ms 785780 KB Output is correct
4 Correct 2115 ms 786828 KB Output is correct
5 Correct 2106 ms 786832 KB Output is correct
6 Correct 688 ms 614800 KB Output is correct
7 Correct 843 ms 637464 KB Output is correct
8 Correct 891 ms 640328 KB Output is correct
9 Correct 611 ms 588408 KB Output is correct
10 Correct 559 ms 588424 KB Output is correct
11 Correct 578 ms 588424 KB Output is correct
12 Correct 533 ms 588408 KB Output is correct
13 Correct 534 ms 588360 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 588408 KB Output is correct
2 Correct 537 ms 588520 KB Output is correct
3 Correct 533 ms 588516 KB Output is correct
4 Correct 536 ms 588564 KB Output is correct
5 Correct 533 ms 588344 KB Output is correct
6 Correct 538 ms 588472 KB Output is correct
7 Correct 537 ms 588408 KB Output is correct
8 Correct 534 ms 588452 KB Output is correct
9 Correct 575 ms 588432 KB Output is correct
10 Correct 537 ms 588580 KB Output is correct
11 Correct 537 ms 588560 KB Output is correct
12 Correct 537 ms 588408 KB Output is correct
13 Correct 529 ms 588448 KB Output is correct
14 Correct 565 ms 588412 KB Output is correct
15 Correct 533 ms 588408 KB Output is correct
16 Correct 545 ms 588372 KB Output is correct
17 Correct 568 ms 589064 KB Output is correct
18 Correct 535 ms 589020 KB Output is correct
19 Correct 537 ms 589048 KB Output is correct
20 Correct 536 ms 588680 KB Output is correct
21 Correct 537 ms 589128 KB Output is correct
22 Correct 558 ms 589040 KB Output is correct
23 Correct 533 ms 589048 KB Output is correct
24 Correct 565 ms 588792 KB Output is correct
25 Correct 576 ms 592744 KB Output is correct
26 Correct 555 ms 592848 KB Output is correct
27 Correct 553 ms 592700 KB Output is correct
28 Correct 551 ms 590140 KB Output is correct
29 Correct 559 ms 592400 KB Output is correct
30 Correct 553 ms 592580 KB Output is correct
31 Correct 555 ms 592352 KB Output is correct
32 Correct 569 ms 592244 KB Output is correct
33 Correct 659 ms 616956 KB Output is correct
34 Correct 701 ms 617092 KB Output is correct
35 Correct 629 ms 616952 KB Output is correct
36 Correct 686 ms 617076 KB Output is correct
37 Correct 748 ms 639992 KB Output is correct
38 Correct 748 ms 639776 KB Output is correct
39 Correct 736 ms 640008 KB Output is correct
40 Correct 787 ms 636676 KB Output is correct
41 Correct 691 ms 604736 KB Output is correct
42 Correct 709 ms 611216 KB Output is correct
43 Correct 874 ms 638060 KB Output is correct
44 Correct 853 ms 639468 KB Output is correct
45 Correct 680 ms 613860 KB Output is correct
46 Correct 676 ms 613916 KB Output is correct
47 Correct 801 ms 635640 KB Output is correct
48 Correct 817 ms 635820 KB Output is correct
49 Correct 553 ms 589144 KB Output is correct
50 Correct 538 ms 588896 KB Output is correct
51 Correct 532 ms 588436 KB Output is correct
52 Correct 532 ms 588340 KB Output is correct
53 Correct 538 ms 588868 KB Output is correct
54 Correct 535 ms 588992 KB Output is correct
55 Correct 539 ms 588948 KB Output is correct
56 Correct 546 ms 588852 KB Output is correct
57 Correct 554 ms 588800 KB Output is correct
58 Correct 615 ms 588408 KB Output is correct
59 Correct 536 ms 588676 KB Output is correct
60 Correct 567 ms 588304 KB Output is correct
61 Correct 1217 ms 680252 KB Output is correct
62 Correct 2087 ms 785780 KB Output is correct
63 Correct 2115 ms 786828 KB Output is correct
64 Correct 2106 ms 786832 KB Output is correct
65 Correct 688 ms 614800 KB Output is correct
66 Correct 843 ms 637464 KB Output is correct
67 Correct 891 ms 640328 KB Output is correct
68 Correct 2407 ms 931580 KB Output is correct
69 Correct 2929 ms 931724 KB Output is correct
70 Correct 1898 ms 931724 KB Output is correct
71 Correct 2435 ms 931720 KB Output is correct
72 Runtime error 1584 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Halted 0 ms 0 KB -