oj.uz

Submission #143585

# Submission time Handle Problem Language Result Execution time Memory
143585 2019-08-14T16:49:20 Z icypiggy Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 601188 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];
//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) {
    //cout << tmp[left][right].first << " " << tmp[left][right].second << " " << left << " " << right << " " << row << "\n";
    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));
                //cout << "hmap update: " << i << " " << left << " " << tmp[left][right].second << " " << right << "\n";
            }
        }
        tmp[left][right] = make_pair(row, row);
    } else {
        tmp[left][right].second++;
    }
}
void update_val2(int left, int right, int row) {
    //cout << tmp[left][right].first << " " << tmp[left][right].second << " " << left << " " << right << " " << row << "\n";
    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));
                //cout << "vmap update: " << left << " " << i << " " << right << " " << tmp[left][right].second << "\n";

            }
        }
        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) {

                //h_seg[r][s.top()+1].push_back(make_pair(i-1, true));
                //cout << "attempt update: " << r << " " << s.top()+1 << " " << i-1 << "\n";
                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) {
            //h_seg[r][s.top()+1].push_back(make_pair(i-1, true));
            update_val(s.top()+1, i-1, r);
            //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";
                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) {
            //v_seg[r][s.top()+1].push_back(make_pair(i-1, true));
            //cout << r << " " << s.top()+1 << " " << i-1 << "\n";
            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);
        }
    }
    /*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());
        }
    }

    fenwick f[a.size()];
    for(int i=0; i<a.size(); i++) {
        f[i].reset();
    }

    long long ans = 0;
    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;
                            f[down].update(p.first, 1);
                            updates.push_back(make_pair(down,p.first));
                            down++;
                        } else {
                            break;
                        }
                    }
                    f[down].update(p.first, 1);
                    updates.push_back(make_pair(down,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;
            }
        }
        for(auto p: updates) {
            f[p.first].update(p.second, -1);
        }
    }*/
    long long ans = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<a[0].size(); j++) {
            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";
                    }
                }
            }
        }
    }

    return ans;
}

Compilation message

rect.cpp: In function 'void gen_h_seg(std::vector<int>&, int)':
rect.cpp:48: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:101: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:129:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:143:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:145:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:225:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:226: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 475 ms 356868 KB Output is correct
2 Correct 474 ms 356728 KB Output is correct
3 Correct 471 ms 356856 KB Output is correct
4 Correct 474 ms 356772 KB Output is correct
5 Correct 479 ms 356828 KB Output is correct
6 Correct 475 ms 356600 KB Output is correct
7 Correct 476 ms 356728 KB Output is correct
8 Correct 473 ms 356600 KB Output is correct
9 Correct 476 ms 356692 KB Output is correct
10 Correct 480 ms 356764 KB Output is correct
11 Correct 475 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 484 ms 356724 KB Output is correct
14 Correct 475 ms 356720 KB Output is correct
15 Correct 482 ms 356760 KB Output is correct
16 Correct 480 ms 356728 KB Output is correct
17 Correct 476 ms 356696 KB Output is correct
18 Correct 478 ms 356720 KB Output is correct
19 Correct 475 ms 356776 KB Output is correct
20 Correct 474 ms 356600 KB Output is correct
21 Correct 484 ms 356768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 356868 KB Output is correct
2 Correct 474 ms 356728 KB Output is correct
3 Correct 471 ms 356856 KB Output is correct
4 Correct 474 ms 356772 KB Output is correct
5 Correct 479 ms 356828 KB Output is correct
6 Correct 475 ms 356600 KB Output is correct
7 Correct 476 ms 356728 KB Output is correct
8 Correct 473 ms 356600 KB Output is correct
9 Correct 476 ms 356692 KB Output is correct
10 Correct 480 ms 356764 KB Output is correct
11 Correct 475 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 484 ms 356724 KB Output is correct
14 Correct 475 ms 356720 KB Output is correct
15 Correct 482 ms 356760 KB Output is correct
16 Correct 480 ms 356728 KB Output is correct
17 Correct 480 ms 356984 KB Output is correct
18 Correct 480 ms 357112 KB Output is correct
19 Correct 472 ms 357116 KB Output is correct
20 Correct 473 ms 356748 KB Output is correct
21 Correct 475 ms 356856 KB Output is correct
22 Correct 476 ms 357112 KB Output is correct
23 Correct 476 ms 357112 KB Output is correct
24 Correct 472 ms 356728 KB Output is correct
25 Correct 476 ms 356696 KB Output is correct
26 Correct 478 ms 356720 KB Output is correct
27 Correct 475 ms 356776 KB Output is correct
28 Correct 474 ms 356600 KB Output is correct
29 Correct 484 ms 356768 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 356868 KB Output is correct
2 Correct 474 ms 356728 KB Output is correct
3 Correct 471 ms 356856 KB Output is correct
4 Correct 474 ms 356772 KB Output is correct
5 Correct 479 ms 356828 KB Output is correct
6 Correct 475 ms 356600 KB Output is correct
7 Correct 476 ms 356728 KB Output is correct
8 Correct 473 ms 356600 KB Output is correct
9 Correct 476 ms 356692 KB Output is correct
10 Correct 480 ms 356764 KB Output is correct
11 Correct 475 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 484 ms 356724 KB Output is correct
14 Correct 475 ms 356720 KB Output is correct
15 Correct 482 ms 356760 KB Output is correct
16 Correct 480 ms 356728 KB Output is correct
17 Correct 480 ms 356984 KB Output is correct
18 Correct 480 ms 357112 KB Output is correct
19 Correct 472 ms 357116 KB Output is correct
20 Correct 473 ms 356748 KB Output is correct
21 Correct 475 ms 356856 KB Output is correct
22 Correct 476 ms 357112 KB Output is correct
23 Correct 476 ms 357112 KB Output is correct
24 Correct 472 ms 356728 KB Output is correct
25 Correct 488 ms 359532 KB Output is correct
26 Correct 488 ms 359544 KB Output is correct
27 Correct 499 ms 359636 KB Output is correct
28 Correct 479 ms 357840 KB Output is correct
29 Correct 489 ms 358520 KB Output is correct
30 Correct 489 ms 358380 KB Output is correct
31 Correct 484 ms 358264 KB Output is correct
32 Correct 489 ms 358352 KB Output is correct
33 Correct 476 ms 356696 KB Output is correct
34 Correct 478 ms 356720 KB Output is correct
35 Correct 475 ms 356776 KB Output is correct
36 Correct 474 ms 356600 KB Output is correct
37 Correct 484 ms 356768 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 356868 KB Output is correct
2 Correct 474 ms 356728 KB Output is correct
3 Correct 471 ms 356856 KB Output is correct
4 Correct 474 ms 356772 KB Output is correct
5 Correct 479 ms 356828 KB Output is correct
6 Correct 475 ms 356600 KB Output is correct
7 Correct 476 ms 356728 KB Output is correct
8 Correct 473 ms 356600 KB Output is correct
9 Correct 476 ms 356692 KB Output is correct
10 Correct 480 ms 356764 KB Output is correct
11 Correct 475 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 484 ms 356724 KB Output is correct
14 Correct 475 ms 356720 KB Output is correct
15 Correct 482 ms 356760 KB Output is correct
16 Correct 480 ms 356728 KB Output is correct
17 Correct 480 ms 356984 KB Output is correct
18 Correct 480 ms 357112 KB Output is correct
19 Correct 472 ms 357116 KB Output is correct
20 Correct 473 ms 356748 KB Output is correct
21 Correct 475 ms 356856 KB Output is correct
22 Correct 476 ms 357112 KB Output is correct
23 Correct 476 ms 357112 KB Output is correct
24 Correct 472 ms 356728 KB Output is correct
25 Correct 488 ms 359532 KB Output is correct
26 Correct 488 ms 359544 KB Output is correct
27 Correct 499 ms 359636 KB Output is correct
28 Correct 479 ms 357840 KB Output is correct
29 Correct 489 ms 358520 KB Output is correct
30 Correct 489 ms 358380 KB Output is correct
31 Correct 484 ms 358264 KB Output is correct
32 Correct 489 ms 358352 KB Output is correct
33 Correct 556 ms 375800 KB Output is correct
34 Correct 605 ms 371176 KB Output is correct
35 Correct 546 ms 371064 KB Output is correct
36 Correct 632 ms 366356 KB Output is correct
37 Correct 645 ms 391028 KB Output is correct
38 Correct 626 ms 391064 KB Output is correct
39 Correct 673 ms 391292 KB Output is correct
40 Correct 652 ms 388828 KB Output is correct
41 Correct 564 ms 368248 KB Output is correct
42 Correct 599 ms 370812 KB Output is correct
43 Correct 709 ms 378872 KB Output is correct
44 Correct 758 ms 378876 KB Output is correct
45 Correct 599 ms 367740 KB Output is correct
46 Correct 588 ms 367736 KB Output is correct
47 Correct 687 ms 377336 KB Output is correct
48 Correct 701 ms 377504 KB Output is correct
49 Correct 476 ms 356696 KB Output is correct
50 Correct 478 ms 356720 KB Output is correct
51 Correct 475 ms 356776 KB Output is correct
52 Correct 474 ms 356600 KB Output is correct
53 Correct 484 ms 356768 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 477 ms 357124 KB Output is correct
2 Correct 478 ms 357000 KB Output is correct
3 Correct 477 ms 356788 KB Output is correct
4 Correct 475 ms 356652 KB Output is correct
5 Correct 544 ms 356856 KB Output is correct
6 Correct 551 ms 356984 KB Output is correct
7 Correct 480 ms 356856 KB Output is correct
8 Correct 475 ms 356956 KB Output is correct
9 Correct 492 ms 356920 KB Output is correct
10 Correct 508 ms 356788 KB Output is correct
11 Correct 481 ms 356728 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 356780 KB Output is correct
2 Correct 1079 ms 424340 KB Output is correct
3 Correct 1851 ms 503332 KB Output is correct
4 Correct 1855 ms 504104 KB Output is correct
5 Correct 1952 ms 504184 KB Output is correct
6 Correct 596 ms 381008 KB Output is correct
7 Correct 696 ms 402680 KB Output is correct
8 Correct 726 ms 405840 KB Output is correct
9 Correct 476 ms 356696 KB Output is correct
10 Correct 478 ms 356720 KB Output is correct
11 Correct 475 ms 356776 KB Output is correct
12 Correct 474 ms 356600 KB Output is correct
13 Correct 484 ms 356768 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 356868 KB Output is correct
2 Correct 474 ms 356728 KB Output is correct
3 Correct 471 ms 356856 KB Output is correct
4 Correct 474 ms 356772 KB Output is correct
5 Correct 479 ms 356828 KB Output is correct
6 Correct 475 ms 356600 KB Output is correct
7 Correct 476 ms 356728 KB Output is correct
8 Correct 473 ms 356600 KB Output is correct
9 Correct 476 ms 356692 KB Output is correct
10 Correct 480 ms 356764 KB Output is correct
11 Correct 475 ms 356728 KB Output is correct
12 Correct 475 ms 356728 KB Output is correct
13 Correct 484 ms 356724 KB Output is correct
14 Correct 475 ms 356720 KB Output is correct
15 Correct 482 ms 356760 KB Output is correct
16 Correct 480 ms 356728 KB Output is correct
17 Correct 480 ms 356984 KB Output is correct
18 Correct 480 ms 357112 KB Output is correct
19 Correct 472 ms 357116 KB Output is correct
20 Correct 473 ms 356748 KB Output is correct
21 Correct 475 ms 356856 KB Output is correct
22 Correct 476 ms 357112 KB Output is correct
23 Correct 476 ms 357112 KB Output is correct
24 Correct 472 ms 356728 KB Output is correct
25 Correct 488 ms 359532 KB Output is correct
26 Correct 488 ms 359544 KB Output is correct
27 Correct 499 ms 359636 KB Output is correct
28 Correct 479 ms 357840 KB Output is correct
29 Correct 489 ms 358520 KB Output is correct
30 Correct 489 ms 358380 KB Output is correct
31 Correct 484 ms 358264 KB Output is correct
32 Correct 489 ms 358352 KB Output is correct
33 Correct 556 ms 375800 KB Output is correct
34 Correct 605 ms 371176 KB Output is correct
35 Correct 546 ms 371064 KB Output is correct
36 Correct 632 ms 366356 KB Output is correct
37 Correct 645 ms 391028 KB Output is correct
38 Correct 626 ms 391064 KB Output is correct
39 Correct 673 ms 391292 KB Output is correct
40 Correct 652 ms 388828 KB Output is correct
41 Correct 564 ms 368248 KB Output is correct
42 Correct 599 ms 370812 KB Output is correct
43 Correct 709 ms 378872 KB Output is correct
44 Correct 758 ms 378876 KB Output is correct
45 Correct 599 ms 367740 KB Output is correct
46 Correct 588 ms 367736 KB Output is correct
47 Correct 687 ms 377336 KB Output is correct
48 Correct 701 ms 377504 KB Output is correct
49 Correct 477 ms 357124 KB Output is correct
50 Correct 478 ms 357000 KB Output is correct
51 Correct 477 ms 356788 KB Output is correct
52 Correct 475 ms 356652 KB Output is correct
53 Correct 544 ms 356856 KB Output is correct
54 Correct 551 ms 356984 KB Output is correct
55 Correct 480 ms 356856 KB Output is correct
56 Correct 475 ms 356956 KB Output is correct
57 Correct 492 ms 356920 KB Output is correct
58 Correct 508 ms 356788 KB Output is correct
59 Correct 481 ms 356728 KB Output is correct
60 Correct 488 ms 356780 KB Output is correct
61 Correct 1079 ms 424340 KB Output is correct
62 Correct 1851 ms 503332 KB Output is correct
63 Correct 1855 ms 504104 KB Output is correct
64 Correct 1952 ms 504184 KB Output is correct
65 Correct 596 ms 381008 KB Output is correct
66 Correct 696 ms 402680 KB Output is correct
67 Correct 726 ms 405840 KB Output is correct
68 Correct 2023 ms 601188 KB Output is correct
69 Correct 2293 ms 535408 KB Output is correct
70 Correct 1533 ms 535344 KB Output is correct
71 Execution timed out 5118 ms 469360 KB Time limit exceeded
72 Halted 0 ms 0 KB -