oj.uz

Submission #143595

# Submission time Handle Problem Language Result Execution time Memory
143595 2019-08-14T17:18:47 Z icypiggy Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 601308 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
#include <assert.h>
using namespace std;
const int n_max = 2550; // make it not lag
vector<pair<int,int>> h_map[n_max][n_max];
vector<pair<int,int>> v_map[n_max][n_max];
//vector<pair<int,int>> v_map2[n_max];
pair<int,int> tmp[n_max][n_max]; // start and end
void update_val(int left, int right, int row) {
    if(tmp[left][right].second != row-1) {
        if(tmp[left][right].second!=-2) {
            for(int i=tmp[left][right].first; i<=tmp[left][right].second; i++) {
                h_map[i][left].push_back(make_pair(tmp[left][right].second, right));
            }
        }
        tmp[left][right] = make_pair(row, row);
    } else {
        tmp[left][right].second++;
    }
}
void update_val2(int left, int right, int row) {
    if(tmp[left][right].second != row-1) {
        if(tmp[left][right].second!=-2) {
            for(int i=tmp[left][right].first; i<=tmp[left][right].second; i++) {

                v_map[left][i].push_back(make_pair(right, tmp[left][right].second));
            }
        }
        tmp[left][right] = make_pair(row, row);
    } else {
        tmp[left][right].second++;
    }
}
stack<int> s;
void gen_h_seg(vector<int> &x, int r) {
    s.push(0);
    for(int i=1; i<x.size(); i++) {
        while(!s.empty() && x[s.top()]<x[i]) {
            if(s.top()!=i-1) {
                update_val(s.top()+1, i-1, r);

            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            update_val(s.top()+1, i-1, r);
        }
        s.push(i);
    }
    while(!s.empty()) s.pop();
}
int fwbit[n_max][n_max];
int fwa[n_max][n_max];
int fw_pt = 0;
struct fenwick {
    int *BIT;
    int *a;
    int n;
    fenwick(): n(n_max) {}
    void reset() {
        BIT = fwbit[fw_pt];
        a = fwa[fw_pt];
        fw_pt++;
    }
    void update(int x, int delta)
    {
          for(; x <= n; x += x&-x)
            BIT[x] += delta;
    }
    int query(int x) {
         int sum = 0;
         for(; x > 0; x -= x&-x)
            sum += BIT[x];
         return sum;
    }
    int query(int x, int y) {
        return query(y)-query(x-1);
    }
};
void gen_v_seg(vector<int> &x, int r) {
    s.push(0);
    for(int i=1; i<x.size(); i++) {
        while(!s.empty() && x[s.top()]<x[i]) {
            if(s.top()!=i-1) {
                update_val2(s.top()+1, i-1, r);
            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            update_val2(s.top()+1, i-1, r);
        }
        s.push(i);
    }
    while(!s.empty()) s.pop();
}

long long count_rectangles(vector<vector<int>> a) {
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<n_max; j++) {
            tmp[i][j] = make_pair(-2,-2);
        }
    }
    for(int i=0; i<a.size(); i++) {
        gen_h_seg(a[i],i);
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<=i; j++) {
            update_val(j,i,1e5);
        }
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<n_max; j++) {
            tmp[i][j] = make_pair(-2,-2);
        }
    }
    //cout << "\n";
    for(int i=0; i<a[0].size(); i++) {
        vector<int> tmp;
        for(int j=0; j<a.size(); j++) {
            tmp.push_back(a[j][i]);
        }
        gen_v_seg(tmp, i);
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<=i; j++) {
            update_val2(j,i,1e5);
        }
    }
    fenwick f;
    f.reset();
    long long ans = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<a[0].size(); j++) {
            if(v_map[i][j].size()>5 && h_map[i][j].size()>5) {
                for(auto &p: h_map[i][j]) {
                    for(auto &q: v_map[i][j]) {
                        if(p.first>=q.first && p.second<=q.second) {
                            ans++;
                            //cout << i << " " << j << " " << q.first << " " << p.second << "\n";
                        }
                    }
                }
            } else {
                auto it = v_map[i][j].begin();
                sort(h_map[i][j].begin(), h_map[i][j].end());
                for(auto &p: h_map[i][j]) {
                    f.update(p.second, 1);
                }
                sort(v_map[i][j].begin(), v_map[i][j].end());
                for(auto &p: h_map[i][j]) {
                    while(it!=v_map[i][j].end() && it->first<=p.first) {
                        ans+=f.query(it->second);
                        it++;
                    }
                    f.update(p.second, -1);
                }
            }
        }
    }
    return ans;
}

Compilation message

rect.cpp: In function 'void gen_h_seg(std::vector<int>&, int)':
rect.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<x.size(); i++) {
                  ~^~~~~~~~~
rect.cpp: In function 'void gen_v_seg(std::vector<int>&, int)':
rect.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<x.size(); i++) {
                  ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:127:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:129:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:142:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:143:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a[0].size(); j++) {
                      ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 356600 KB Output is correct
2 Correct 467 ms 356776 KB Output is correct
3 Correct 469 ms 356752 KB Output is correct
4 Correct 472 ms 356648 KB Output is correct
5 Correct 467 ms 356572 KB Output is correct
6 Correct 473 ms 356760 KB Output is correct
7 Correct 493 ms 356728 KB Output is correct
8 Correct 476 ms 356700 KB Output is correct
9 Correct 473 ms 356728 KB Output is correct
10 Correct 475 ms 356784 KB Output is correct
11 Correct 472 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 472 ms 356732 KB Output is correct
14 Correct 480 ms 356856 KB Output is correct
15 Correct 478 ms 356792 KB Output is correct
16 Correct 568 ms 356764 KB Output is correct
17 Correct 469 ms 356732 KB Output is correct
18 Correct 470 ms 356648 KB Output is correct
19 Correct 470 ms 356728 KB Output is correct
20 Correct 473 ms 356600 KB Output is correct
21 Correct 472 ms 356728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 356600 KB Output is correct
2 Correct 467 ms 356776 KB Output is correct
3 Correct 469 ms 356752 KB Output is correct
4 Correct 472 ms 356648 KB Output is correct
5 Correct 467 ms 356572 KB Output is correct
6 Correct 473 ms 356760 KB Output is correct
7 Correct 493 ms 356728 KB Output is correct
8 Correct 476 ms 356700 KB Output is correct
9 Correct 473 ms 356728 KB Output is correct
10 Correct 475 ms 356784 KB Output is correct
11 Correct 472 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 472 ms 356732 KB Output is correct
14 Correct 480 ms 356856 KB Output is correct
15 Correct 478 ms 356792 KB Output is correct
16 Correct 568 ms 356764 KB Output is correct
17 Correct 473 ms 357112 KB Output is correct
18 Correct 470 ms 357112 KB Output is correct
19 Correct 474 ms 357112 KB Output is correct
20 Correct 497 ms 356988 KB Output is correct
21 Correct 481 ms 357080 KB Output is correct
22 Correct 486 ms 356996 KB Output is correct
23 Correct 477 ms 356844 KB Output is correct
24 Correct 472 ms 356784 KB Output is correct
25 Correct 469 ms 356732 KB Output is correct
26 Correct 470 ms 356648 KB Output is correct
27 Correct 470 ms 356728 KB Output is correct
28 Correct 473 ms 356600 KB Output is correct
29 Correct 472 ms 356728 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 356600 KB Output is correct
2 Correct 467 ms 356776 KB Output is correct
3 Correct 469 ms 356752 KB Output is correct
4 Correct 472 ms 356648 KB Output is correct
5 Correct 467 ms 356572 KB Output is correct
6 Correct 473 ms 356760 KB Output is correct
7 Correct 493 ms 356728 KB Output is correct
8 Correct 476 ms 356700 KB Output is correct
9 Correct 473 ms 356728 KB Output is correct
10 Correct 475 ms 356784 KB Output is correct
11 Correct 472 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 472 ms 356732 KB Output is correct
14 Correct 480 ms 356856 KB Output is correct
15 Correct 478 ms 356792 KB Output is correct
16 Correct 568 ms 356764 KB Output is correct
17 Correct 473 ms 357112 KB Output is correct
18 Correct 470 ms 357112 KB Output is correct
19 Correct 474 ms 357112 KB Output is correct
20 Correct 497 ms 356988 KB Output is correct
21 Correct 481 ms 357080 KB Output is correct
22 Correct 486 ms 356996 KB Output is correct
23 Correct 477 ms 356844 KB Output is correct
24 Correct 472 ms 356784 KB Output is correct
25 Correct 490 ms 359580 KB Output is correct
26 Correct 486 ms 359416 KB Output is correct
27 Correct 486 ms 359416 KB Output is correct
28 Correct 478 ms 357864 KB Output is correct
29 Correct 488 ms 358544 KB Output is correct
30 Correct 490 ms 358372 KB Output is correct
31 Correct 504 ms 358472 KB Output is correct
32 Correct 499 ms 358264 KB Output is correct
33 Correct 469 ms 356732 KB Output is correct
34 Correct 470 ms 356648 KB Output is correct
35 Correct 470 ms 356728 KB Output is correct
36 Correct 473 ms 356600 KB Output is correct
37 Correct 472 ms 356728 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 356600 KB Output is correct
2 Correct 467 ms 356776 KB Output is correct
3 Correct 469 ms 356752 KB Output is correct
4 Correct 472 ms 356648 KB Output is correct
5 Correct 467 ms 356572 KB Output is correct
6 Correct 473 ms 356760 KB Output is correct
7 Correct 493 ms 356728 KB Output is correct
8 Correct 476 ms 356700 KB Output is correct
9 Correct 473 ms 356728 KB Output is correct
10 Correct 475 ms 356784 KB Output is correct
11 Correct 472 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 472 ms 356732 KB Output is correct
14 Correct 480 ms 356856 KB Output is correct
15 Correct 478 ms 356792 KB Output is correct
16 Correct 568 ms 356764 KB Output is correct
17 Correct 473 ms 357112 KB Output is correct
18 Correct 470 ms 357112 KB Output is correct
19 Correct 474 ms 357112 KB Output is correct
20 Correct 497 ms 356988 KB Output is correct
21 Correct 481 ms 357080 KB Output is correct
22 Correct 486 ms 356996 KB Output is correct
23 Correct 477 ms 356844 KB Output is correct
24 Correct 472 ms 356784 KB Output is correct
25 Correct 490 ms 359580 KB Output is correct
26 Correct 486 ms 359416 KB Output is correct
27 Correct 486 ms 359416 KB Output is correct
28 Correct 478 ms 357864 KB Output is correct
29 Correct 488 ms 358544 KB Output is correct
30 Correct 490 ms 358372 KB Output is correct
31 Correct 504 ms 358472 KB Output is correct
32 Correct 499 ms 358264 KB Output is correct
33 Correct 571 ms 375904 KB Output is correct
34 Correct 595 ms 371136 KB Output is correct
35 Correct 541 ms 371076 KB Output is correct
36 Correct 633 ms 366392 KB Output is correct
37 Correct 656 ms 391288 KB Output is correct
38 Correct 753 ms 390960 KB Output is correct
39 Correct 646 ms 391208 KB Output is correct
40 Correct 637 ms 388896 KB Output is correct
41 Correct 658 ms 368404 KB Output is correct
42 Correct 677 ms 370868 KB Output is correct
43 Correct 760 ms 378700 KB Output is correct
44 Correct 759 ms 378904 KB Output is correct
45 Correct 610 ms 367768 KB Output is correct
46 Correct 605 ms 367608 KB Output is correct
47 Correct 759 ms 377304 KB Output is correct
48 Correct 731 ms 377376 KB Output is correct
49 Correct 469 ms 356732 KB Output is correct
50 Correct 470 ms 356648 KB Output is correct
51 Correct 470 ms 356728 KB Output is correct
52 Correct 473 ms 356600 KB Output is correct
53 Correct 472 ms 356728 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 357040 KB Output is correct
2 Correct 474 ms 356996 KB Output is correct
3 Correct 475 ms 356892 KB Output is correct
4 Correct 470 ms 356668 KB Output is correct
5 Correct 478 ms 356928 KB Output is correct
6 Correct 478 ms 356984 KB Output is correct
7 Correct 485 ms 357008 KB Output is correct
8 Correct 479 ms 356904 KB Output is correct
9 Correct 472 ms 356892 KB Output is correct
10 Correct 480 ms 356780 KB Output is correct
11 Correct 470 ms 356728 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 356704 KB Output is correct
2 Correct 1201 ms 424432 KB Output is correct
3 Correct 2115 ms 503540 KB Output is correct
4 Correct 2168 ms 504168 KB Output is correct
5 Correct 2115 ms 504176 KB Output is correct
6 Correct 588 ms 381016 KB Output is correct
7 Correct 712 ms 402880 KB Output is correct
8 Correct 742 ms 406008 KB Output is correct
9 Correct 469 ms 356732 KB Output is correct
10 Correct 470 ms 356648 KB Output is correct
11 Correct 470 ms 356728 KB Output is correct
12 Correct 473 ms 356600 KB Output is correct
13 Correct 472 ms 356728 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 468 ms 356600 KB Output is correct
2 Correct 467 ms 356776 KB Output is correct
3 Correct 469 ms 356752 KB Output is correct
4 Correct 472 ms 356648 KB Output is correct
5 Correct 467 ms 356572 KB Output is correct
6 Correct 473 ms 356760 KB Output is correct
7 Correct 493 ms 356728 KB Output is correct
8 Correct 476 ms 356700 KB Output is correct
9 Correct 473 ms 356728 KB Output is correct
10 Correct 475 ms 356784 KB Output is correct
11 Correct 472 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 472 ms 356732 KB Output is correct
14 Correct 480 ms 356856 KB Output is correct
15 Correct 478 ms 356792 KB Output is correct
16 Correct 568 ms 356764 KB Output is correct
17 Correct 473 ms 357112 KB Output is correct
18 Correct 470 ms 357112 KB Output is correct
19 Correct 474 ms 357112 KB Output is correct
20 Correct 497 ms 356988 KB Output is correct
21 Correct 481 ms 357080 KB Output is correct
22 Correct 486 ms 356996 KB Output is correct
23 Correct 477 ms 356844 KB Output is correct
24 Correct 472 ms 356784 KB Output is correct
25 Correct 490 ms 359580 KB Output is correct
26 Correct 486 ms 359416 KB Output is correct
27 Correct 486 ms 359416 KB Output is correct
28 Correct 478 ms 357864 KB Output is correct
29 Correct 488 ms 358544 KB Output is correct
30 Correct 490 ms 358372 KB Output is correct
31 Correct 504 ms 358472 KB Output is correct
32 Correct 499 ms 358264 KB Output is correct
33 Correct 571 ms 375904 KB Output is correct
34 Correct 595 ms 371136 KB Output is correct
35 Correct 541 ms 371076 KB Output is correct
36 Correct 633 ms 366392 KB Output is correct
37 Correct 656 ms 391288 KB Output is correct
38 Correct 753 ms 390960 KB Output is correct
39 Correct 646 ms 391208 KB Output is correct
40 Correct 637 ms 388896 KB Output is correct
41 Correct 658 ms 368404 KB Output is correct
42 Correct 677 ms 370868 KB Output is correct
43 Correct 760 ms 378700 KB Output is correct
44 Correct 759 ms 378904 KB Output is correct
45 Correct 610 ms 367768 KB Output is correct
46 Correct 605 ms 367608 KB Output is correct
47 Correct 759 ms 377304 KB Output is correct
48 Correct 731 ms 377376 KB Output is correct
49 Correct 483 ms 357040 KB Output is correct
50 Correct 474 ms 356996 KB Output is correct
51 Correct 475 ms 356892 KB Output is correct
52 Correct 470 ms 356668 KB Output is correct
53 Correct 478 ms 356928 KB Output is correct
54 Correct 478 ms 356984 KB Output is correct
55 Correct 485 ms 357008 KB Output is correct
56 Correct 479 ms 356904 KB Output is correct
57 Correct 472 ms 356892 KB Output is correct
58 Correct 480 ms 356780 KB Output is correct
59 Correct 470 ms 356728 KB Output is correct
60 Correct 490 ms 356704 KB Output is correct
61 Correct 1201 ms 424432 KB Output is correct
62 Correct 2115 ms 503540 KB Output is correct
63 Correct 2168 ms 504168 KB Output is correct
64 Correct 2115 ms 504176 KB Output is correct
65 Correct 588 ms 381016 KB Output is correct
66 Correct 712 ms 402880 KB Output is correct
67 Correct 742 ms 406008 KB Output is correct
68 Correct 2101 ms 601308 KB Output is correct
69 Correct 2410 ms 535496 KB Output is correct
70 Correct 1657 ms 535276 KB Output is correct
71 Execution timed out 5034 ms 469376 KB Time limit exceeded
72 Halted 0 ms 0 KB -