oj.uz

Submission #154448

# Submission time Handle Problem Language Result Execution time Memory
154448 2019-09-21T22:30:12 Z crackersamdjam Rectangles (IOI19_rect) C++14
72 / 100
 2942 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;

int first[MM], last[MM], bit[MM], stl;
std::pair<int, int> st[MM];
std::vector<std::pair<int, int>> vec(MM);
std::map<int, int, std::greater<int>> hor[MM][MM], vert[MM][MM];

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

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.push_back({x.first-j+1, x.second}); //adjust
            sort(vec.begin(), vec.end(), [](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 < vec.size() && bf <= vec[l].second)
                    update(vec[l++].first, 1);
                ans += query(b.second);
            }
            
            while(l)
                update(vec[--l].first, -1);
            
            vec.clear();
        }
    }
    
    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)
 */

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:111:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l < vec.size() && bf <= vec[l].second)
                       ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588388 KB Output is correct
2 Correct 546 ms 588432 KB Output is correct
3 Correct 536 ms 588640 KB Output is correct
4 Correct 532 ms 588380 KB Output is correct
5 Correct 536 ms 588412 KB Output is correct
6 Correct 542 ms 588408 KB Output is correct
7 Correct 532 ms 588488 KB Output is correct
8 Correct 589 ms 588376 KB Output is correct
9 Correct 610 ms 588412 KB Output is correct
10 Correct 594 ms 588456 KB Output is correct
11 Correct 533 ms 588516 KB Output is correct
12 Correct 529 ms 588408 KB Output is correct
13 Correct 531 ms 588384 KB Output is correct
14 Correct 533 ms 588408 KB Output is correct
15 Correct 532 ms 588408 KB Output is correct
16 Correct 585 ms 588484 KB Output is correct
17 Correct 530 ms 588408 KB Output is correct
18 Correct 538 ms 588360 KB Output is correct
19 Correct 535 ms 588420 KB Output is correct
20 Correct 531 ms 588464 KB Output is correct
21 Correct 535 ms 588664 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588388 KB Output is correct
2 Correct 546 ms 588432 KB Output is correct
3 Correct 536 ms 588640 KB Output is correct
4 Correct 532 ms 588380 KB Output is correct
5 Correct 536 ms 588412 KB Output is correct
6 Correct 542 ms 588408 KB Output is correct
7 Correct 532 ms 588488 KB Output is correct
8 Correct 589 ms 588376 KB Output is correct
9 Correct 610 ms 588412 KB Output is correct
10 Correct 594 ms 588456 KB Output is correct
11 Correct 533 ms 588516 KB Output is correct
12 Correct 529 ms 588408 KB Output is correct
13 Correct 531 ms 588384 KB Output is correct
14 Correct 533 ms 588408 KB Output is correct
15 Correct 532 ms 588408 KB Output is correct
16 Correct 585 ms 588484 KB Output is correct
17 Correct 537 ms 589044 KB Output is correct
18 Correct 534 ms 589108 KB Output is correct
19 Correct 536 ms 589028 KB Output is correct
20 Correct 548 ms 588800 KB Output is correct
21 Correct 593 ms 589052 KB Output is correct
22 Correct 534 ms 589052 KB Output is correct
23 Correct 576 ms 589000 KB Output is correct
24 Correct 534 ms 588716 KB Output is correct
25 Correct 530 ms 588408 KB Output is correct
26 Correct 538 ms 588360 KB Output is correct
27 Correct 535 ms 588420 KB Output is correct
28 Correct 531 ms 588464 KB Output is correct
29 Correct 535 ms 588664 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588388 KB Output is correct
2 Correct 546 ms 588432 KB Output is correct
3 Correct 536 ms 588640 KB Output is correct
4 Correct 532 ms 588380 KB Output is correct
5 Correct 536 ms 588412 KB Output is correct
6 Correct 542 ms 588408 KB Output is correct
7 Correct 532 ms 588488 KB Output is correct
8 Correct 589 ms 588376 KB Output is correct
9 Correct 610 ms 588412 KB Output is correct
10 Correct 594 ms 588456 KB Output is correct
11 Correct 533 ms 588516 KB Output is correct
12 Correct 529 ms 588408 KB Output is correct
13 Correct 531 ms 588384 KB Output is correct
14 Correct 533 ms 588408 KB Output is correct
15 Correct 532 ms 588408 KB Output is correct
16 Correct 585 ms 588484 KB Output is correct
17 Correct 537 ms 589044 KB Output is correct
18 Correct 534 ms 589108 KB Output is correct
19 Correct 536 ms 589028 KB Output is correct
20 Correct 548 ms 588800 KB Output is correct
21 Correct 593 ms 589052 KB Output is correct
22 Correct 534 ms 589052 KB Output is correct
23 Correct 576 ms 589000 KB Output is correct
24 Correct 534 ms 588716 KB Output is correct
25 Correct 572 ms 592860 KB Output is correct
26 Correct 550 ms 592624 KB Output is correct
27 Correct 556 ms 592752 KB Output is correct
28 Correct 545 ms 590152 KB Output is correct
29 Correct 593 ms 592408 KB Output is correct
30 Correct 567 ms 592548 KB Output is correct
31 Correct 567 ms 592508 KB Output is correct
32 Correct 549 ms 592504 KB Output is correct
33 Correct 530 ms 588408 KB Output is correct
34 Correct 538 ms 588360 KB Output is correct
35 Correct 535 ms 588420 KB Output is correct
36 Correct 531 ms 588464 KB Output is correct
37 Correct 535 ms 588664 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588388 KB Output is correct
2 Correct 546 ms 588432 KB Output is correct
3 Correct 536 ms 588640 KB Output is correct
4 Correct 532 ms 588380 KB Output is correct
5 Correct 536 ms 588412 KB Output is correct
6 Correct 542 ms 588408 KB Output is correct
7 Correct 532 ms 588488 KB Output is correct
8 Correct 589 ms 588376 KB Output is correct
9 Correct 610 ms 588412 KB Output is correct
10 Correct 594 ms 588456 KB Output is correct
11 Correct 533 ms 588516 KB Output is correct
12 Correct 529 ms 588408 KB Output is correct
13 Correct 531 ms 588384 KB Output is correct
14 Correct 533 ms 588408 KB Output is correct
15 Correct 532 ms 588408 KB Output is correct
16 Correct 585 ms 588484 KB Output is correct
17 Correct 537 ms 589044 KB Output is correct
18 Correct 534 ms 589108 KB Output is correct
19 Correct 536 ms 589028 KB Output is correct
20 Correct 548 ms 588800 KB Output is correct
21 Correct 593 ms 589052 KB Output is correct
22 Correct 534 ms 589052 KB Output is correct
23 Correct 576 ms 589000 KB Output is correct
24 Correct 534 ms 588716 KB Output is correct
25 Correct 572 ms 592860 KB Output is correct
26 Correct 550 ms 592624 KB Output is correct
27 Correct 556 ms 592752 KB Output is correct
28 Correct 545 ms 590152 KB Output is correct
29 Correct 593 ms 592408 KB Output is correct
30 Correct 567 ms 592548 KB Output is correct
31 Correct 567 ms 592508 KB Output is correct
32 Correct 549 ms 592504 KB Output is correct
33 Correct 667 ms 617144 KB Output is correct
34 Correct 692 ms 617212 KB Output is correct
35 Correct 629 ms 617080 KB Output is correct
36 Correct 667 ms 617096 KB Output is correct
37 Correct 753 ms 640120 KB Output is correct
38 Correct 787 ms 640136 KB Output is correct
39 Correct 794 ms 640104 KB Output is correct
40 Correct 761 ms 636792 KB Output is correct
41 Correct 646 ms 604780 KB Output is correct
42 Correct 686 ms 611076 KB Output is correct
43 Correct 829 ms 638496 KB Output is correct
44 Correct 876 ms 639340 KB Output is correct
45 Correct 673 ms 614392 KB Output is correct
46 Correct 674 ms 614296 KB Output is correct
47 Correct 808 ms 635676 KB Output is correct
48 Correct 828 ms 635756 KB Output is correct
49 Correct 530 ms 588408 KB Output is correct
50 Correct 538 ms 588360 KB Output is correct
51 Correct 535 ms 588420 KB Output is correct
52 Correct 531 ms 588464 KB Output is correct
53 Correct 535 ms 588664 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 589048 KB Output is correct
2 Correct 535 ms 588996 KB Output is correct
3 Correct 529 ms 588424 KB Output is correct
4 Correct 533 ms 588368 KB Output is correct
5 Correct 534 ms 588868 KB Output is correct
6 Correct 574 ms 588852 KB Output is correct
7 Correct 543 ms 588872 KB Output is correct
8 Correct 564 ms 588924 KB Output is correct
9 Correct 531 ms 588920 KB Output is correct
10 Correct 549 ms 588608 KB Output is correct
11 Correct 594 ms 588804 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 588368 KB Output is correct
2 Correct 1259 ms 680004 KB Output is correct
3 Correct 2133 ms 784740 KB Output is correct
4 Correct 2237 ms 785536 KB Output is correct
5 Correct 2115 ms 785784 KB Output is correct
6 Correct 678 ms 613996 KB Output is correct
7 Correct 849 ms 636804 KB Output is correct
8 Correct 853 ms 639176 KB Output is correct
9 Correct 530 ms 588408 KB Output is correct
10 Correct 538 ms 588360 KB Output is correct
11 Correct 535 ms 588420 KB Output is correct
12 Correct 531 ms 588464 KB Output is correct
13 Correct 535 ms 588664 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588388 KB Output is correct
2 Correct 546 ms 588432 KB Output is correct
3 Correct 536 ms 588640 KB Output is correct
4 Correct 532 ms 588380 KB Output is correct
5 Correct 536 ms 588412 KB Output is correct
6 Correct 542 ms 588408 KB Output is correct
7 Correct 532 ms 588488 KB Output is correct
8 Correct 589 ms 588376 KB Output is correct
9 Correct 610 ms 588412 KB Output is correct
10 Correct 594 ms 588456 KB Output is correct
11 Correct 533 ms 588516 KB Output is correct
12 Correct 529 ms 588408 KB Output is correct
13 Correct 531 ms 588384 KB Output is correct
14 Correct 533 ms 588408 KB Output is correct
15 Correct 532 ms 588408 KB Output is correct
16 Correct 585 ms 588484 KB Output is correct
17 Correct 537 ms 589044 KB Output is correct
18 Correct 534 ms 589108 KB Output is correct
19 Correct 536 ms 589028 KB Output is correct
20 Correct 548 ms 588800 KB Output is correct
21 Correct 593 ms 589052 KB Output is correct
22 Correct 534 ms 589052 KB Output is correct
23 Correct 576 ms 589000 KB Output is correct
24 Correct 534 ms 588716 KB Output is correct
25 Correct 572 ms 592860 KB Output is correct
26 Correct 550 ms 592624 KB Output is correct
27 Correct 556 ms 592752 KB Output is correct
28 Correct 545 ms 590152 KB Output is correct
29 Correct 593 ms 592408 KB Output is correct
30 Correct 567 ms 592548 KB Output is correct
31 Correct 567 ms 592508 KB Output is correct
32 Correct 549 ms 592504 KB Output is correct
33 Correct 667 ms 617144 KB Output is correct
34 Correct 692 ms 617212 KB Output is correct
35 Correct 629 ms 617080 KB Output is correct
36 Correct 667 ms 617096 KB Output is correct
37 Correct 753 ms 640120 KB Output is correct
38 Correct 787 ms 640136 KB Output is correct
39 Correct 794 ms 640104 KB Output is correct
40 Correct 761 ms 636792 KB Output is correct
41 Correct 646 ms 604780 KB Output is correct
42 Correct 686 ms 611076 KB Output is correct
43 Correct 829 ms 638496 KB Output is correct
44 Correct 876 ms 639340 KB Output is correct
45 Correct 673 ms 614392 KB Output is correct
46 Correct 674 ms 614296 KB Output is correct
47 Correct 808 ms 635676 KB Output is correct
48 Correct 828 ms 635756 KB Output is correct
49 Correct 532 ms 589048 KB Output is correct
50 Correct 535 ms 588996 KB Output is correct
51 Correct 529 ms 588424 KB Output is correct
52 Correct 533 ms 588368 KB Output is correct
53 Correct 534 ms 588868 KB Output is correct
54 Correct 574 ms 588852 KB Output is correct
55 Correct 543 ms 588872 KB Output is correct
56 Correct 564 ms 588924 KB Output is correct
57 Correct 531 ms 588920 KB Output is correct
58 Correct 549 ms 588608 KB Output is correct
59 Correct 594 ms 588804 KB Output is correct
60 Correct 656 ms 588368 KB Output is correct
61 Correct 1259 ms 680004 KB Output is correct
62 Correct 2133 ms 784740 KB Output is correct
63 Correct 2237 ms 785536 KB Output is correct
64 Correct 2115 ms 785784 KB Output is correct
65 Correct 678 ms 613996 KB Output is correct
66 Correct 849 ms 636804 KB Output is correct
67 Correct 853 ms 639176 KB Output is correct
68 Correct 2367 ms 931492 KB Output is correct
69 Correct 2942 ms 931292 KB Output is correct
70 Correct 1970 ms 930756 KB Output is correct
71 Correct 2482 ms 930828 KB Output is correct
72 Runtime error 1675 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Halted 0 ms 0 KB -