oj.uz

Submission #143539

# Submission time Handle Problem Language Result Execution time Memory
143539 2019-08-14T14:20:13 Z icypiggy Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 910668 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,bool>> h_seg[n_max][n_max];
vector<pair<int,bool>> v_seg[n_max][n_max];
//vector<pair<int,int>> h_map[n_max][n_max];
vector<pair<int,int>> v_map[n_max][n_max];

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) {
                h_seg[r][s.top()+1].push_back(make_pair(i-1, true));
                //cout << r << " " << s.top()+1 << " " << i-1 << "\n";
            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            h_seg[r][s.top()+1].push_back(make_pair(i-1, true));
            //cout << r << " " << s.top()+1 << " " << i-1 << "\n";
        }
        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) {
                v_seg[r][s.top()+1].push_back(make_pair(i-1, true));
                //cout << r << " " << s.top()+1 << " " << i-1 << "\n";
            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            v_seg[r][s.top()+1].push_back(make_pair(i-1, true));
            //cout << r << " " << s.top()+1 << " " << i-1 << "\n";
        }
        s.push(i);
    }
    while(!s.empty()) s.pop();
}

long long count_rectangles(vector<vector<int>> a) {
    for(int i=0; i<a.size(); i++) {
        gen_h_seg(a[i],i);
    }
    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<a.size(); i++) {
        for(int j=0; j<a[0].size(); j++) {
            sort(h_seg[i][j].begin(), h_seg[i][j].end());
            sort(v_seg[j][i].begin(), v_seg[j][i].end());
        }
    }


    for(int i=a[0].size()-1; i>=0; i--) {
        for(int j=a.size()-1; j>=0; j--) {
            for(auto p: v_map[i][j]) {
                for(int k=i+1; k<=p.second; k++) {
                    v_map[k][j].push_back(p);
                    //cout << "k,j,p: " << k << " " << j << " " << p.first << " " << p.second << "\n";
                }
            }
        }
    }
    fenwick f[a.size()];
    for(int i=0; i<a.size(); i++) {
        f[i].reset();
    }

    long long ans = 0;
    vector<pair<int,int>> v_map2[n_max];
    for(int j=0; j<a[0].size(); j++) {
        vector<pair<int,int>> updates;
        for(int i=0; i<a.size(); i++) {
            for(auto &p: h_seg[i][j]) {
                if(p.second) {
                    int down = i;
                    while(down+1!=a.size()) {
                        auto it = lower_bound(h_seg[down+1][j].begin(), h_seg[down+1][j].end(), make_pair(p.first,true));
                        if(it==h_seg[down+1][j].end()) break;
                        if(*it==make_pair(p.first, true)) {
                            it->second = false;
                            down++;
                        } else {
                            break;
                        }
                    }
                    for(int k=i; k<=down; k++) {
                        f[k].update(p.first, 1);
                        //cout << "fenwick update: " << i << " " << j << " " << k << " " << p.first << "\n";
                        updates.push_back(make_pair(k,p.first));
                    }

                }
            }
            swap(i,j);
            for(auto &p: v_seg[i][j]) {
                if(p.second) {
                    int down = i;
                    while(down+1!=a[0].size()) {
                        auto it = lower_bound(v_seg[down+1][j].begin(), v_seg[down+1][j].end(), make_pair(p.first,true));
                        if(it==v_seg[down+1][j].end()) break;
                        if(*it==make_pair(p.first, true)) {
                            it->second = false;
                            down++;
                        } else {
                            break;
                        }
                    }
                    v_map2[j].push_back(make_pair(p.first, down));
                    //cout << "i,j,p.first,down(v): " << i << " " << j << " " << p.first << " " << down << "\n";
                }
            }
            swap(i,j);
            for(int a=0; a<v_map2[i].size(); a++) {
                while(a<v_map2[i].size() && v_map2[i][a].second<j) {
                    swap(v_map2[i][a], v_map2[i][v_map2[i].size()-1]);
                    v_map2[i].pop_back();
                }
            }
            for(auto q: v_map2[i]) {
                int tmp = f[q.first].query(j,q.second);
                ans += tmp;
                assert(tmp>=0);
                //cout << "query: " << i << " " << j << " " << q.first << " " << q.second << "\n";
                //cout << "ans changed by " << tmp << " queried: " << q.first << " " << i << " " << q.second << "\n";
            }

            //h_seg[i][j].clear();
        }
        for(auto p: updates) {
            f[p.first].update(p.second, -1);
            //cout << "undo increment: " << p.first << " " << p.second << "\n";
        }
    }
    /*
    if(0) {
        for(int i=0; i<a[0].size(); i++) {
            vector<pair<int,int>> updates;
            for(int j=0; j<a.size(); j++) {
                //cout << "coordinate: " << i << " " << j << "\n";
                for(auto p: h_map[j][i]) {
                    for(int k=j; k<=p.second; k++) {
                        f[k].update(p.first, 1);
                        //cout << "updated: " << k << "-th fenwick, position " << p.first << "increased by 1.\n";
                        updates.push_back(make_pair(k, p.first));
                    }
                }

            }
            for(auto p: updates) {
                f[p.first].update(p.second, -1);
                //cout << "undo increment: " << p.first << " " << p.second << "\n";
            }
        }
    }*/
    //cout << "ans: " << ans << "\n";
    return ans;
}

Compilation message

rect.cpp: In function 'void gen_h_seg(std::vector<int>&, int)':
rect.cpp:17: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:66: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:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:90:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:92:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:98:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a[0].size(); j++) {
                      ~^~~~~~~~~~~~
rect.cpp:116:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<a[0].size(); j++) {
                  ~^~~~~~~~~~~~
rect.cpp:124:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<a.size(); i++) {
                      ~^~~~~~~~~
rect.cpp:128:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(down+1!=a.size()) {
                           ~~~~~~^~~~~~~~~~
rect.cpp:150:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(down+1!=a[0].size()) {
                           ~~~~~~^~~~~~~~~~~~~
rect.cpp:165:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int a=0; a<v_map2[i].size(); a++) {
                          ~^~~~~~~~~~~~~~~~~
rect.cpp:166:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(a<v_map2[i].size() && v_map2[i][a].second<j) {
                       ~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 458524 KB Output is correct
2 Correct 422 ms 458832 KB Output is correct
3 Correct 411 ms 458848 KB Output is correct
4 Correct 410 ms 458940 KB Output is correct
5 Correct 416 ms 458488 KB Output is correct
6 Correct 433 ms 458932 KB Output is correct
7 Correct 427 ms 458904 KB Output is correct
8 Correct 431 ms 458624 KB Output is correct
9 Correct 414 ms 458844 KB Output is correct
10 Correct 438 ms 458872 KB Output is correct
11 Correct 434 ms 458844 KB Output is correct
12 Correct 415 ms 458936 KB Output is correct
13 Correct 429 ms 458544 KB Output is correct
14 Correct 410 ms 458488 KB Output is correct
15 Correct 415 ms 458488 KB Output is correct
16 Correct 408 ms 458744 KB Output is correct
17 Correct 413 ms 458488 KB Output is correct
18 Correct 408 ms 458488 KB Output is correct
19 Correct 412 ms 458872 KB Output is correct
20 Correct 410 ms 458604 KB Output is correct
21 Correct 409 ms 458492 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 458524 KB Output is correct
2 Correct 422 ms 458832 KB Output is correct
3 Correct 411 ms 458848 KB Output is correct
4 Correct 410 ms 458940 KB Output is correct
5 Correct 416 ms 458488 KB Output is correct
6 Correct 433 ms 458932 KB Output is correct
7 Correct 427 ms 458904 KB Output is correct
8 Correct 431 ms 458624 KB Output is correct
9 Correct 414 ms 458844 KB Output is correct
10 Correct 438 ms 458872 KB Output is correct
11 Correct 434 ms 458844 KB Output is correct
12 Correct 415 ms 458936 KB Output is correct
13 Correct 429 ms 458544 KB Output is correct
14 Correct 410 ms 458488 KB Output is correct
15 Correct 415 ms 458488 KB Output is correct
16 Correct 408 ms 458744 KB Output is correct
17 Correct 416 ms 459652 KB Output is correct
18 Correct 415 ms 459864 KB Output is correct
19 Correct 412 ms 459756 KB Output is correct
20 Correct 415 ms 459472 KB Output is correct
21 Correct 413 ms 459540 KB Output is correct
22 Correct 417 ms 459608 KB Output is correct
23 Correct 417 ms 459600 KB Output is correct
24 Correct 411 ms 459540 KB Output is correct
25 Correct 413 ms 458488 KB Output is correct
26 Correct 408 ms 458488 KB Output is correct
27 Correct 412 ms 458872 KB Output is correct
28 Correct 410 ms 458604 KB Output is correct
29 Correct 409 ms 458492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 458524 KB Output is correct
2 Correct 422 ms 458832 KB Output is correct
3 Correct 411 ms 458848 KB Output is correct
4 Correct 410 ms 458940 KB Output is correct
5 Correct 416 ms 458488 KB Output is correct
6 Correct 433 ms 458932 KB Output is correct
7 Correct 427 ms 458904 KB Output is correct
8 Correct 431 ms 458624 KB Output is correct
9 Correct 414 ms 458844 KB Output is correct
10 Correct 438 ms 458872 KB Output is correct
11 Correct 434 ms 458844 KB Output is correct
12 Correct 415 ms 458936 KB Output is correct
13 Correct 429 ms 458544 KB Output is correct
14 Correct 410 ms 458488 KB Output is correct
15 Correct 415 ms 458488 KB Output is correct
16 Correct 408 ms 458744 KB Output is correct
17 Correct 416 ms 459652 KB Output is correct
18 Correct 415 ms 459864 KB Output is correct
19 Correct 412 ms 459756 KB Output is correct
20 Correct 415 ms 459472 KB Output is correct
21 Correct 413 ms 459540 KB Output is correct
22 Correct 417 ms 459608 KB Output is correct
23 Correct 417 ms 459600 KB Output is correct
24 Correct 411 ms 459540 KB Output is correct
25 Correct 423 ms 463352 KB Output is correct
26 Correct 435 ms 463352 KB Output is correct
27 Correct 472 ms 463472 KB Output is correct
28 Correct 420 ms 461688 KB Output is correct
29 Correct 428 ms 462312 KB Output is correct
30 Correct 434 ms 462236 KB Output is correct
31 Correct 429 ms 462348 KB Output is correct
32 Correct 433 ms 462200 KB Output is correct
33 Correct 413 ms 458488 KB Output is correct
34 Correct 408 ms 458488 KB Output is correct
35 Correct 412 ms 458872 KB Output is correct
36 Correct 410 ms 458604 KB Output is correct
37 Correct 409 ms 458492 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 458524 KB Output is correct
2 Correct 422 ms 458832 KB Output is correct
3 Correct 411 ms 458848 KB Output is correct
4 Correct 410 ms 458940 KB Output is correct
5 Correct 416 ms 458488 KB Output is correct
6 Correct 433 ms 458932 KB Output is correct
7 Correct 427 ms 458904 KB Output is correct
8 Correct 431 ms 458624 KB Output is correct
9 Correct 414 ms 458844 KB Output is correct
10 Correct 438 ms 458872 KB Output is correct
11 Correct 434 ms 458844 KB Output is correct
12 Correct 415 ms 458936 KB Output is correct
13 Correct 429 ms 458544 KB Output is correct
14 Correct 410 ms 458488 KB Output is correct
15 Correct 415 ms 458488 KB Output is correct
16 Correct 408 ms 458744 KB Output is correct
17 Correct 416 ms 459652 KB Output is correct
18 Correct 415 ms 459864 KB Output is correct
19 Correct 412 ms 459756 KB Output is correct
20 Correct 415 ms 459472 KB Output is correct
21 Correct 413 ms 459540 KB Output is correct
22 Correct 417 ms 459608 KB Output is correct
23 Correct 417 ms 459600 KB Output is correct
24 Correct 411 ms 459540 KB Output is correct
25 Correct 423 ms 463352 KB Output is correct
26 Correct 435 ms 463352 KB Output is correct
27 Correct 472 ms 463472 KB Output is correct
28 Correct 420 ms 461688 KB Output is correct
29 Correct 428 ms 462312 KB Output is correct
30 Correct 434 ms 462236 KB Output is correct
31 Correct 429 ms 462348 KB Output is correct
32 Correct 433 ms 462200 KB Output is correct
33 Correct 563 ms 484624 KB Output is correct
34 Correct 526 ms 479872 KB Output is correct
35 Correct 549 ms 482748 KB Output is correct
36 Correct 509 ms 477928 KB Output is correct
37 Correct 671 ms 499512 KB Output is correct
38 Correct 674 ms 499724 KB Output is correct
39 Correct 679 ms 499544 KB Output is correct
40 Correct 648 ms 496940 KB Output is correct
41 Correct 526 ms 477020 KB Output is correct
42 Correct 563 ms 479816 KB Output is correct
43 Correct 676 ms 487492 KB Output is correct
44 Correct 681 ms 487660 KB Output is correct
45 Correct 550 ms 476736 KB Output is correct
46 Correct 540 ms 473120 KB Output is correct
47 Correct 665 ms 486300 KB Output is correct
48 Correct 670 ms 486264 KB Output is correct
49 Correct 413 ms 458488 KB Output is correct
50 Correct 408 ms 458488 KB Output is correct
51 Correct 412 ms 458872 KB Output is correct
52 Correct 410 ms 458604 KB Output is correct
53 Correct 409 ms 458492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 458920 KB Output is correct
2 Correct 415 ms 458888 KB Output is correct
3 Correct 412 ms 458540 KB Output is correct
4 Correct 407 ms 458488 KB Output is correct
5 Correct 424 ms 458908 KB Output is correct
6 Correct 412 ms 458824 KB Output is correct
7 Correct 420 ms 458652 KB Output is correct
8 Correct 415 ms 458672 KB Output is correct
9 Correct 414 ms 458900 KB Output is correct
10 Correct 411 ms 458480 KB Output is correct
11 Correct 417 ms 458828 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 458664 KB Output is correct
2 Correct 1071 ms 538616 KB Output is correct
3 Correct 1918 ms 630392 KB Output is correct
4 Correct 1959 ms 631052 KB Output is correct
5 Correct 1953 ms 631196 KB Output is correct
6 Correct 684 ms 482812 KB Output is correct
7 Correct 1018 ms 504856 KB Output is correct
8 Correct 1031 ms 507804 KB Output is correct
9 Correct 413 ms 458488 KB Output is correct
10 Correct 408 ms 458488 KB Output is correct
11 Correct 412 ms 458872 KB Output is correct
12 Correct 410 ms 458604 KB Output is correct
13 Correct 409 ms 458492 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 458524 KB Output is correct
2 Correct 422 ms 458832 KB Output is correct
3 Correct 411 ms 458848 KB Output is correct
4 Correct 410 ms 458940 KB Output is correct
5 Correct 416 ms 458488 KB Output is correct
6 Correct 433 ms 458932 KB Output is correct
7 Correct 427 ms 458904 KB Output is correct
8 Correct 431 ms 458624 KB Output is correct
9 Correct 414 ms 458844 KB Output is correct
10 Correct 438 ms 458872 KB Output is correct
11 Correct 434 ms 458844 KB Output is correct
12 Correct 415 ms 458936 KB Output is correct
13 Correct 429 ms 458544 KB Output is correct
14 Correct 410 ms 458488 KB Output is correct
15 Correct 415 ms 458488 KB Output is correct
16 Correct 408 ms 458744 KB Output is correct
17 Correct 416 ms 459652 KB Output is correct
18 Correct 415 ms 459864 KB Output is correct
19 Correct 412 ms 459756 KB Output is correct
20 Correct 415 ms 459472 KB Output is correct
21 Correct 413 ms 459540 KB Output is correct
22 Correct 417 ms 459608 KB Output is correct
23 Correct 417 ms 459600 KB Output is correct
24 Correct 411 ms 459540 KB Output is correct
25 Correct 423 ms 463352 KB Output is correct
26 Correct 435 ms 463352 KB Output is correct
27 Correct 472 ms 463472 KB Output is correct
28 Correct 420 ms 461688 KB Output is correct
29 Correct 428 ms 462312 KB Output is correct
30 Correct 434 ms 462236 KB Output is correct
31 Correct 429 ms 462348 KB Output is correct
32 Correct 433 ms 462200 KB Output is correct
33 Correct 563 ms 484624 KB Output is correct
34 Correct 526 ms 479872 KB Output is correct
35 Correct 549 ms 482748 KB Output is correct
36 Correct 509 ms 477928 KB Output is correct
37 Correct 671 ms 499512 KB Output is correct
38 Correct 674 ms 499724 KB Output is correct
39 Correct 679 ms 499544 KB Output is correct
40 Correct 648 ms 496940 KB Output is correct
41 Correct 526 ms 477020 KB Output is correct
42 Correct 563 ms 479816 KB Output is correct
43 Correct 676 ms 487492 KB Output is correct
44 Correct 681 ms 487660 KB Output is correct
45 Correct 550 ms 476736 KB Output is correct
46 Correct 540 ms 473120 KB Output is correct
47 Correct 665 ms 486300 KB Output is correct
48 Correct 670 ms 486264 KB Output is correct
49 Correct 415 ms 458920 KB Output is correct
50 Correct 415 ms 458888 KB Output is correct
51 Correct 412 ms 458540 KB Output is correct
52 Correct 407 ms 458488 KB Output is correct
53 Correct 424 ms 458908 KB Output is correct
54 Correct 412 ms 458824 KB Output is correct
55 Correct 420 ms 458652 KB Output is correct
56 Correct 415 ms 458672 KB Output is correct
57 Correct 414 ms 458900 KB Output is correct
58 Correct 411 ms 458480 KB Output is correct
59 Correct 417 ms 458828 KB Output is correct
60 Correct 416 ms 458664 KB Output is correct
61 Correct 1071 ms 538616 KB Output is correct
62 Correct 1918 ms 630392 KB Output is correct
63 Correct 1959 ms 631052 KB Output is correct
64 Correct 1953 ms 631196 KB Output is correct
65 Correct 684 ms 482812 KB Output is correct
66 Correct 1018 ms 504856 KB Output is correct
67 Correct 1031 ms 507804 KB Output is correct
68 Correct 2429 ms 721836 KB Output is correct
69 Correct 1952 ms 657236 KB Output is correct
70 Correct 2274 ms 685132 KB Output is correct
71 Correct 1657 ms 620380 KB Output is correct
72 Execution timed out 5137 ms 910668 KB Time limit exceeded
73 Halted 0 ms 0 KB -