oj.uz

답안 #143596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143596 2019-08-14T17:20:42 Z icypiggy Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 601316 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()>3 && h_map[i][j].size()>3) {
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 356760 KB Output is correct
2 Correct 478 ms 356696 KB Output is correct
3 Correct 473 ms 356816 KB Output is correct
4 Correct 474 ms 356844 KB Output is correct
5 Correct 473 ms 356840 KB Output is correct
6 Correct 468 ms 356728 KB Output is correct
7 Correct 471 ms 356692 KB Output is correct
8 Correct 473 ms 356648 KB Output is correct
9 Correct 471 ms 356728 KB Output is correct
10 Correct 475 ms 356764 KB Output is correct
11 Correct 472 ms 356620 KB Output is correct
12 Correct 473 ms 356772 KB Output is correct
13 Correct 471 ms 356660 KB Output is correct
14 Correct 471 ms 356644 KB Output is correct
15 Correct 469 ms 356668 KB Output is correct
16 Correct 476 ms 356728 KB Output is correct
17 Correct 479 ms 356784 KB Output is correct
18 Correct 471 ms 356600 KB Output is correct
19 Correct 471 ms 356728 KB Output is correct
20 Correct 470 ms 356620 KB Output is correct
21 Correct 470 ms 356600 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 356760 KB Output is correct
2 Correct 478 ms 356696 KB Output is correct
3 Correct 473 ms 356816 KB Output is correct
4 Correct 474 ms 356844 KB Output is correct
5 Correct 473 ms 356840 KB Output is correct
6 Correct 468 ms 356728 KB Output is correct
7 Correct 471 ms 356692 KB Output is correct
8 Correct 473 ms 356648 KB Output is correct
9 Correct 471 ms 356728 KB Output is correct
10 Correct 475 ms 356764 KB Output is correct
11 Correct 472 ms 356620 KB Output is correct
12 Correct 473 ms 356772 KB Output is correct
13 Correct 471 ms 356660 KB Output is correct
14 Correct 471 ms 356644 KB Output is correct
15 Correct 469 ms 356668 KB Output is correct
16 Correct 476 ms 356728 KB Output is correct
17 Correct 505 ms 357192 KB Output is correct
18 Correct 478 ms 357208 KB Output is correct
19 Correct 480 ms 357112 KB Output is correct
20 Correct 477 ms 356856 KB Output is correct
21 Correct 475 ms 356996 KB Output is correct
22 Correct 473 ms 356976 KB Output is correct
23 Correct 483 ms 356948 KB Output is correct
24 Correct 469 ms 356728 KB Output is correct
25 Correct 479 ms 356784 KB Output is correct
26 Correct 471 ms 356600 KB Output is correct
27 Correct 471 ms 356728 KB Output is correct
28 Correct 470 ms 356620 KB Output is correct
29 Correct 470 ms 356600 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 356760 KB Output is correct
2 Correct 478 ms 356696 KB Output is correct
3 Correct 473 ms 356816 KB Output is correct
4 Correct 474 ms 356844 KB Output is correct
5 Correct 473 ms 356840 KB Output is correct
6 Correct 468 ms 356728 KB Output is correct
7 Correct 471 ms 356692 KB Output is correct
8 Correct 473 ms 356648 KB Output is correct
9 Correct 471 ms 356728 KB Output is correct
10 Correct 475 ms 356764 KB Output is correct
11 Correct 472 ms 356620 KB Output is correct
12 Correct 473 ms 356772 KB Output is correct
13 Correct 471 ms 356660 KB Output is correct
14 Correct 471 ms 356644 KB Output is correct
15 Correct 469 ms 356668 KB Output is correct
16 Correct 476 ms 356728 KB Output is correct
17 Correct 505 ms 357192 KB Output is correct
18 Correct 478 ms 357208 KB Output is correct
19 Correct 480 ms 357112 KB Output is correct
20 Correct 477 ms 356856 KB Output is correct
21 Correct 475 ms 356996 KB Output is correct
22 Correct 473 ms 356976 KB Output is correct
23 Correct 483 ms 356948 KB Output is correct
24 Correct 469 ms 356728 KB Output is correct
25 Correct 484 ms 359456 KB Output is correct
26 Correct 491 ms 359456 KB Output is correct
27 Correct 492 ms 359516 KB Output is correct
28 Correct 510 ms 357868 KB Output is correct
29 Correct 489 ms 358436 KB Output is correct
30 Correct 501 ms 358484 KB Output is correct
31 Correct 505 ms 358392 KB Output is correct
32 Correct 488 ms 358204 KB Output is correct
33 Correct 479 ms 356784 KB Output is correct
34 Correct 471 ms 356600 KB Output is correct
35 Correct 471 ms 356728 KB Output is correct
36 Correct 470 ms 356620 KB Output is correct
37 Correct 470 ms 356600 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 356760 KB Output is correct
2 Correct 478 ms 356696 KB Output is correct
3 Correct 473 ms 356816 KB Output is correct
4 Correct 474 ms 356844 KB Output is correct
5 Correct 473 ms 356840 KB Output is correct
6 Correct 468 ms 356728 KB Output is correct
7 Correct 471 ms 356692 KB Output is correct
8 Correct 473 ms 356648 KB Output is correct
9 Correct 471 ms 356728 KB Output is correct
10 Correct 475 ms 356764 KB Output is correct
11 Correct 472 ms 356620 KB Output is correct
12 Correct 473 ms 356772 KB Output is correct
13 Correct 471 ms 356660 KB Output is correct
14 Correct 471 ms 356644 KB Output is correct
15 Correct 469 ms 356668 KB Output is correct
16 Correct 476 ms 356728 KB Output is correct
17 Correct 505 ms 357192 KB Output is correct
18 Correct 478 ms 357208 KB Output is correct
19 Correct 480 ms 357112 KB Output is correct
20 Correct 477 ms 356856 KB Output is correct
21 Correct 475 ms 356996 KB Output is correct
22 Correct 473 ms 356976 KB Output is correct
23 Correct 483 ms 356948 KB Output is correct
24 Correct 469 ms 356728 KB Output is correct
25 Correct 484 ms 359456 KB Output is correct
26 Correct 491 ms 359456 KB Output is correct
27 Correct 492 ms 359516 KB Output is correct
28 Correct 510 ms 357868 KB Output is correct
29 Correct 489 ms 358436 KB Output is correct
30 Correct 501 ms 358484 KB Output is correct
31 Correct 505 ms 358392 KB Output is correct
32 Correct 488 ms 358204 KB Output is correct
33 Correct 571 ms 375876 KB Output is correct
34 Correct 568 ms 371080 KB Output is correct
35 Correct 542 ms 371308 KB Output is correct
36 Correct 646 ms 366284 KB Output is correct
37 Correct 647 ms 391160 KB Output is correct
38 Correct 646 ms 391032 KB Output is correct
39 Correct 648 ms 390992 KB Output is correct
40 Correct 637 ms 388984 KB Output is correct
41 Correct 575 ms 368192 KB Output is correct
42 Correct 622 ms 370872 KB Output is correct
43 Correct 751 ms 378800 KB Output is correct
44 Correct 768 ms 378872 KB Output is correct
45 Correct 610 ms 367736 KB Output is correct
46 Correct 612 ms 367712 KB Output is correct
47 Correct 730 ms 377404 KB Output is correct
48 Correct 731 ms 377464 KB Output is correct
49 Correct 479 ms 356784 KB Output is correct
50 Correct 471 ms 356600 KB Output is correct
51 Correct 471 ms 356728 KB Output is correct
52 Correct 470 ms 356620 KB Output is correct
53 Correct 470 ms 356600 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 476 ms 357040 KB Output is correct
2 Correct 471 ms 356956 KB Output is correct
3 Correct 469 ms 356728 KB Output is correct
4 Correct 469 ms 356624 KB Output is correct
5 Correct 497 ms 356984 KB Output is correct
6 Correct 479 ms 356916 KB Output is correct
7 Correct 478 ms 356984 KB Output is correct
8 Correct 474 ms 356920 KB Output is correct
9 Correct 499 ms 356948 KB Output is correct
10 Correct 471 ms 356804 KB Output is correct
11 Correct 473 ms 356820 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 469 ms 356664 KB Output is correct
2 Correct 1187 ms 424200 KB Output is correct
3 Correct 2091 ms 503520 KB Output is correct
4 Correct 2107 ms 504184 KB Output is correct
5 Correct 2165 ms 504288 KB Output is correct
6 Correct 584 ms 381024 KB Output is correct
7 Correct 705 ms 402880 KB Output is correct
8 Correct 724 ms 405952 KB Output is correct
9 Correct 479 ms 356784 KB Output is correct
10 Correct 471 ms 356600 KB Output is correct
11 Correct 471 ms 356728 KB Output is correct
12 Correct 470 ms 356620 KB Output is correct
13 Correct 470 ms 356600 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 515 ms 356760 KB Output is correct
2 Correct 478 ms 356696 KB Output is correct
3 Correct 473 ms 356816 KB Output is correct
4 Correct 474 ms 356844 KB Output is correct
5 Correct 473 ms 356840 KB Output is correct
6 Correct 468 ms 356728 KB Output is correct
7 Correct 471 ms 356692 KB Output is correct
8 Correct 473 ms 356648 KB Output is correct
9 Correct 471 ms 356728 KB Output is correct
10 Correct 475 ms 356764 KB Output is correct
11 Correct 472 ms 356620 KB Output is correct
12 Correct 473 ms 356772 KB Output is correct
13 Correct 471 ms 356660 KB Output is correct
14 Correct 471 ms 356644 KB Output is correct
15 Correct 469 ms 356668 KB Output is correct
16 Correct 476 ms 356728 KB Output is correct
17 Correct 505 ms 357192 KB Output is correct
18 Correct 478 ms 357208 KB Output is correct
19 Correct 480 ms 357112 KB Output is correct
20 Correct 477 ms 356856 KB Output is correct
21 Correct 475 ms 356996 KB Output is correct
22 Correct 473 ms 356976 KB Output is correct
23 Correct 483 ms 356948 KB Output is correct
24 Correct 469 ms 356728 KB Output is correct
25 Correct 484 ms 359456 KB Output is correct
26 Correct 491 ms 359456 KB Output is correct
27 Correct 492 ms 359516 KB Output is correct
28 Correct 510 ms 357868 KB Output is correct
29 Correct 489 ms 358436 KB Output is correct
30 Correct 501 ms 358484 KB Output is correct
31 Correct 505 ms 358392 KB Output is correct
32 Correct 488 ms 358204 KB Output is correct
33 Correct 571 ms 375876 KB Output is correct
34 Correct 568 ms 371080 KB Output is correct
35 Correct 542 ms 371308 KB Output is correct
36 Correct 646 ms 366284 KB Output is correct
37 Correct 647 ms 391160 KB Output is correct
38 Correct 646 ms 391032 KB Output is correct
39 Correct 648 ms 390992 KB Output is correct
40 Correct 637 ms 388984 KB Output is correct
41 Correct 575 ms 368192 KB Output is correct
42 Correct 622 ms 370872 KB Output is correct
43 Correct 751 ms 378800 KB Output is correct
44 Correct 768 ms 378872 KB Output is correct
45 Correct 610 ms 367736 KB Output is correct
46 Correct 612 ms 367712 KB Output is correct
47 Correct 730 ms 377404 KB Output is correct
48 Correct 731 ms 377464 KB Output is correct
49 Correct 476 ms 357040 KB Output is correct
50 Correct 471 ms 356956 KB Output is correct
51 Correct 469 ms 356728 KB Output is correct
52 Correct 469 ms 356624 KB Output is correct
53 Correct 497 ms 356984 KB Output is correct
54 Correct 479 ms 356916 KB Output is correct
55 Correct 478 ms 356984 KB Output is correct
56 Correct 474 ms 356920 KB Output is correct
57 Correct 499 ms 356948 KB Output is correct
58 Correct 471 ms 356804 KB Output is correct
59 Correct 473 ms 356820 KB Output is correct
60 Correct 469 ms 356664 KB Output is correct
61 Correct 1187 ms 424200 KB Output is correct
62 Correct 2091 ms 503520 KB Output is correct
63 Correct 2107 ms 504184 KB Output is correct
64 Correct 2165 ms 504288 KB Output is correct
65 Correct 584 ms 381024 KB Output is correct
66 Correct 705 ms 402880 KB Output is correct
67 Correct 724 ms 405952 KB Output is correct
68 Correct 2130 ms 601316 KB Output is correct
69 Correct 2443 ms 535448 KB Output is correct
70 Correct 1670 ms 535400 KB Output is correct
71 Execution timed out 5104 ms 469388 KB Time limit exceeded
72 Halted 0 ms 0 KB -