oj.uz

Submission #154450

# Submission time Handle Problem Language Result Execution time Memory
154450 2019-09-21T22:35:37 Z crackersamdjam Rectangles (IOI19_rect) C++14
72 / 100
 3137 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: 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]){
                if(hor[i+1][j].count(x.first))
                    x.second += hor[i+1][j][x.first];
                vec[vecl++] = {x.first-j+1, x.second};
            }
            sort(vec, vec+vecl, [](const std::pair<int, int> &x, const std::pair<int, int> &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;
}

#ifndef ONLINE_JUDGE
int notmain(){
    
    print(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}})
    );
    
    return 0;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 588372 KB Output is correct
2 Correct 543 ms 588536 KB Output is correct
3 Correct 552 ms 588568 KB Output is correct
4 Correct 567 ms 588504 KB Output is correct
5 Correct 532 ms 588308 KB Output is correct
6 Correct 534 ms 588628 KB Output is correct
7 Correct 532 ms 588516 KB Output is correct
8 Correct 534 ms 588392 KB Output is correct
9 Correct 560 ms 588492 KB Output is correct
10 Correct 532 ms 588636 KB Output is correct
11 Correct 557 ms 588408 KB Output is correct
12 Correct 532 ms 588408 KB Output is correct
13 Correct 535 ms 588384 KB Output is correct
14 Correct 586 ms 588300 KB Output is correct
15 Correct 533 ms 588460 KB Output is correct
16 Correct 531 ms 588408 KB Output is correct
17 Correct 535 ms 588436 KB Output is correct
18 Correct 532 ms 588408 KB Output is correct
19 Correct 536 ms 588396 KB Output is correct
20 Correct 552 ms 588500 KB Output is correct
21 Correct 534 ms 588512 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 588372 KB Output is correct
2 Correct 543 ms 588536 KB Output is correct
3 Correct 552 ms 588568 KB Output is correct
4 Correct 567 ms 588504 KB Output is correct
5 Correct 532 ms 588308 KB Output is correct
6 Correct 534 ms 588628 KB Output is correct
7 Correct 532 ms 588516 KB Output is correct
8 Correct 534 ms 588392 KB Output is correct
9 Correct 560 ms 588492 KB Output is correct
10 Correct 532 ms 588636 KB Output is correct
11 Correct 557 ms 588408 KB Output is correct
12 Correct 532 ms 588408 KB Output is correct
13 Correct 535 ms 588384 KB Output is correct
14 Correct 586 ms 588300 KB Output is correct
15 Correct 533 ms 588460 KB Output is correct
16 Correct 531 ms 588408 KB Output is correct
17 Correct 567 ms 589024 KB Output is correct
18 Correct 596 ms 589160 KB Output is correct
19 Correct 539 ms 589028 KB Output is correct
20 Correct 572 ms 588616 KB Output is correct
21 Correct 569 ms 588996 KB Output is correct
22 Correct 540 ms 589020 KB Output is correct
23 Correct 571 ms 588984 KB Output is correct
24 Correct 539 ms 588620 KB Output is correct
25 Correct 535 ms 588436 KB Output is correct
26 Correct 532 ms 588408 KB Output is correct
27 Correct 536 ms 588396 KB Output is correct
28 Correct 552 ms 588500 KB Output is correct
29 Correct 534 ms 588512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 588372 KB Output is correct
2 Correct 543 ms 588536 KB Output is correct
3 Correct 552 ms 588568 KB Output is correct
4 Correct 567 ms 588504 KB Output is correct
5 Correct 532 ms 588308 KB Output is correct
6 Correct 534 ms 588628 KB Output is correct
7 Correct 532 ms 588516 KB Output is correct
8 Correct 534 ms 588392 KB Output is correct
9 Correct 560 ms 588492 KB Output is correct
10 Correct 532 ms 588636 KB Output is correct
11 Correct 557 ms 588408 KB Output is correct
12 Correct 532 ms 588408 KB Output is correct
13 Correct 535 ms 588384 KB Output is correct
14 Correct 586 ms 588300 KB Output is correct
15 Correct 533 ms 588460 KB Output is correct
16 Correct 531 ms 588408 KB Output is correct
17 Correct 567 ms 589024 KB Output is correct
18 Correct 596 ms 589160 KB Output is correct
19 Correct 539 ms 589028 KB Output is correct
20 Correct 572 ms 588616 KB Output is correct
21 Correct 569 ms 588996 KB Output is correct
22 Correct 540 ms 589020 KB Output is correct
23 Correct 571 ms 588984 KB Output is correct
24 Correct 539 ms 588620 KB Output is correct
25 Correct 549 ms 592664 KB Output is correct
26 Correct 555 ms 592792 KB Output is correct
27 Correct 583 ms 592720 KB Output is correct
28 Correct 601 ms 590228 KB Output is correct
29 Correct 562 ms 592320 KB Output is correct
30 Correct 557 ms 592584 KB Output is correct
31 Correct 561 ms 592200 KB Output is correct
32 Correct 558 ms 592280 KB Output is correct
33 Correct 535 ms 588436 KB Output is correct
34 Correct 532 ms 588408 KB Output is correct
35 Correct 536 ms 588396 KB Output is correct
36 Correct 552 ms 588500 KB Output is correct
37 Correct 534 ms 588512 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 588372 KB Output is correct
2 Correct 543 ms 588536 KB Output is correct
3 Correct 552 ms 588568 KB Output is correct
4 Correct 567 ms 588504 KB Output is correct
5 Correct 532 ms 588308 KB Output is correct
6 Correct 534 ms 588628 KB Output is correct
7 Correct 532 ms 588516 KB Output is correct
8 Correct 534 ms 588392 KB Output is correct
9 Correct 560 ms 588492 KB Output is correct
10 Correct 532 ms 588636 KB Output is correct
11 Correct 557 ms 588408 KB Output is correct
12 Correct 532 ms 588408 KB Output is correct
13 Correct 535 ms 588384 KB Output is correct
14 Correct 586 ms 588300 KB Output is correct
15 Correct 533 ms 588460 KB Output is correct
16 Correct 531 ms 588408 KB Output is correct
17 Correct 567 ms 589024 KB Output is correct
18 Correct 596 ms 589160 KB Output is correct
19 Correct 539 ms 589028 KB Output is correct
20 Correct 572 ms 588616 KB Output is correct
21 Correct 569 ms 588996 KB Output is correct
22 Correct 540 ms 589020 KB Output is correct
23 Correct 571 ms 588984 KB Output is correct
24 Correct 539 ms 588620 KB Output is correct
25 Correct 549 ms 592664 KB Output is correct
26 Correct 555 ms 592792 KB Output is correct
27 Correct 583 ms 592720 KB Output is correct
28 Correct 601 ms 590228 KB Output is correct
29 Correct 562 ms 592320 KB Output is correct
30 Correct 557 ms 592584 KB Output is correct
31 Correct 561 ms 592200 KB Output is correct
32 Correct 558 ms 592280 KB Output is correct
33 Correct 657 ms 616232 KB Output is correct
34 Correct 725 ms 616392 KB Output is correct
35 Correct 647 ms 616328 KB Output is correct
36 Correct 667 ms 616376 KB Output is correct
37 Correct 770 ms 639404 KB Output is correct
38 Correct 854 ms 639324 KB Output is correct
39 Correct 740 ms 639452 KB Output is correct
40 Correct 774 ms 636164 KB Output is correct
41 Correct 646 ms 604160 KB Output is correct
42 Correct 683 ms 610508 KB Output is correct
43 Correct 814 ms 637612 KB Output is correct
44 Correct 827 ms 638444 KB Output is correct
45 Correct 720 ms 613492 KB Output is correct
46 Correct 717 ms 613432 KB Output is correct
47 Correct 879 ms 634376 KB Output is correct
48 Correct 827 ms 634796 KB Output is correct
49 Correct 535 ms 588436 KB Output is correct
50 Correct 532 ms 588408 KB Output is correct
51 Correct 536 ms 588396 KB Output is correct
52 Correct 552 ms 588500 KB Output is correct
53 Correct 534 ms 588512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 592 ms 588972 KB Output is correct
2 Correct 558 ms 589052 KB Output is correct
3 Correct 533 ms 588500 KB Output is correct
4 Correct 569 ms 588432 KB Output is correct
5 Correct 586 ms 588920 KB Output is correct
6 Correct 578 ms 588940 KB Output is correct
7 Correct 557 ms 588852 KB Output is correct
8 Correct 538 ms 589020 KB Output is correct
9 Correct 557 ms 589048 KB Output is correct
10 Correct 552 ms 588648 KB Output is correct
11 Correct 591 ms 588664 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 588316 KB Output is correct
2 Correct 1216 ms 679752 KB Output is correct
3 Correct 2117 ms 786100 KB Output is correct
4 Correct 2091 ms 787564 KB Output is correct
5 Correct 2084 ms 787540 KB Output is correct
6 Correct 672 ms 614468 KB Output is correct
7 Correct 848 ms 637952 KB Output is correct
8 Correct 934 ms 640928 KB Output is correct
9 Correct 535 ms 588436 KB Output is correct
10 Correct 532 ms 588408 KB Output is correct
11 Correct 536 ms 588396 KB Output is correct
12 Correct 552 ms 588500 KB Output is correct
13 Correct 534 ms 588512 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 588372 KB Output is correct
2 Correct 543 ms 588536 KB Output is correct
3 Correct 552 ms 588568 KB Output is correct
4 Correct 567 ms 588504 KB Output is correct
5 Correct 532 ms 588308 KB Output is correct
6 Correct 534 ms 588628 KB Output is correct
7 Correct 532 ms 588516 KB Output is correct
8 Correct 534 ms 588392 KB Output is correct
9 Correct 560 ms 588492 KB Output is correct
10 Correct 532 ms 588636 KB Output is correct
11 Correct 557 ms 588408 KB Output is correct
12 Correct 532 ms 588408 KB Output is correct
13 Correct 535 ms 588384 KB Output is correct
14 Correct 586 ms 588300 KB Output is correct
15 Correct 533 ms 588460 KB Output is correct
16 Correct 531 ms 588408 KB Output is correct
17 Correct 567 ms 589024 KB Output is correct
18 Correct 596 ms 589160 KB Output is correct
19 Correct 539 ms 589028 KB Output is correct
20 Correct 572 ms 588616 KB Output is correct
21 Correct 569 ms 588996 KB Output is correct
22 Correct 540 ms 589020 KB Output is correct
23 Correct 571 ms 588984 KB Output is correct
24 Correct 539 ms 588620 KB Output is correct
25 Correct 549 ms 592664 KB Output is correct
26 Correct 555 ms 592792 KB Output is correct
27 Correct 583 ms 592720 KB Output is correct
28 Correct 601 ms 590228 KB Output is correct
29 Correct 562 ms 592320 KB Output is correct
30 Correct 557 ms 592584 KB Output is correct
31 Correct 561 ms 592200 KB Output is correct
32 Correct 558 ms 592280 KB Output is correct
33 Correct 657 ms 616232 KB Output is correct
34 Correct 725 ms 616392 KB Output is correct
35 Correct 647 ms 616328 KB Output is correct
36 Correct 667 ms 616376 KB Output is correct
37 Correct 770 ms 639404 KB Output is correct
38 Correct 854 ms 639324 KB Output is correct
39 Correct 740 ms 639452 KB Output is correct
40 Correct 774 ms 636164 KB Output is correct
41 Correct 646 ms 604160 KB Output is correct
42 Correct 683 ms 610508 KB Output is correct
43 Correct 814 ms 637612 KB Output is correct
44 Correct 827 ms 638444 KB Output is correct
45 Correct 720 ms 613492 KB Output is correct
46 Correct 717 ms 613432 KB Output is correct
47 Correct 879 ms 634376 KB Output is correct
48 Correct 827 ms 634796 KB Output is correct
49 Correct 592 ms 588972 KB Output is correct
50 Correct 558 ms 589052 KB Output is correct
51 Correct 533 ms 588500 KB Output is correct
52 Correct 569 ms 588432 KB Output is correct
53 Correct 586 ms 588920 KB Output is correct
54 Correct 578 ms 588940 KB Output is correct
55 Correct 557 ms 588852 KB Output is correct
56 Correct 538 ms 589020 KB Output is correct
57 Correct 557 ms 589048 KB Output is correct
58 Correct 552 ms 588648 KB Output is correct
59 Correct 591 ms 588664 KB Output is correct
60 Correct 537 ms 588316 KB Output is correct
61 Correct 1216 ms 679752 KB Output is correct
62 Correct 2117 ms 786100 KB Output is correct
63 Correct 2091 ms 787564 KB Output is correct
64 Correct 2084 ms 787540 KB Output is correct
65 Correct 672 ms 614468 KB Output is correct
66 Correct 848 ms 637952 KB Output is correct
67 Correct 934 ms 640928 KB Output is correct
68 Correct 2713 ms 931728 KB Output is correct
69 Correct 3137 ms 931576 KB Output is correct
70 Correct 1927 ms 931764 KB Output is correct
71 Correct 2534 ms 931720 KB Output is correct
72 Runtime error 1622 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Halted 0 ms 0 KB -