oj.uz

Submission #143741

# Submission time Handle Problem Language Result Execution time Memory
143741 2019-08-15T01:51:58 Z icypiggy Rectangles (IOI19_rect) C++14
38 / 100
 2040 ms 504292 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;
    }

};
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++;
                        }
                    }
                }
            } 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:87: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:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:141: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 489 ms 356728 KB Output is correct
2 Correct 487 ms 356692 KB Output is correct
3 Correct 484 ms 356728 KB Output is correct
4 Correct 485 ms 356728 KB Output is correct
5 Correct 494 ms 356700 KB Output is correct
6 Correct 492 ms 356692 KB Output is correct
7 Correct 481 ms 356728 KB Output is correct
8 Correct 488 ms 356736 KB Output is correct
9 Correct 486 ms 356732 KB Output is correct
10 Correct 594 ms 356856 KB Output is correct
11 Correct 498 ms 356700 KB Output is correct
12 Correct 519 ms 356764 KB Output is correct
13 Correct 505 ms 356728 KB Output is correct
14 Correct 481 ms 356600 KB Output is correct
15 Correct 480 ms 356600 KB Output is correct
16 Correct 488 ms 356572 KB Output is correct
17 Correct 501 ms 356728 KB Output is correct
18 Correct 501 ms 356728 KB Output is correct
19 Correct 481 ms 356660 KB Output is correct
20 Correct 476 ms 356600 KB Output is correct
21 Correct 483 ms 356692 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 356728 KB Output is correct
2 Correct 487 ms 356692 KB Output is correct
3 Correct 484 ms 356728 KB Output is correct
4 Correct 485 ms 356728 KB Output is correct
5 Correct 494 ms 356700 KB Output is correct
6 Correct 492 ms 356692 KB Output is correct
7 Correct 481 ms 356728 KB Output is correct
8 Correct 488 ms 356736 KB Output is correct
9 Correct 486 ms 356732 KB Output is correct
10 Correct 594 ms 356856 KB Output is correct
11 Correct 498 ms 356700 KB Output is correct
12 Correct 519 ms 356764 KB Output is correct
13 Correct 505 ms 356728 KB Output is correct
14 Correct 481 ms 356600 KB Output is correct
15 Correct 480 ms 356600 KB Output is correct
16 Correct 488 ms 356572 KB Output is correct
17 Correct 485 ms 357232 KB Output is correct
18 Correct 483 ms 357080 KB Output is correct
19 Correct 490 ms 357240 KB Output is correct
20 Correct 489 ms 356908 KB Output is correct
21 Correct 494 ms 356956 KB Output is correct
22 Correct 488 ms 356956 KB Output is correct
23 Correct 482 ms 356936 KB Output is correct
24 Correct 517 ms 356984 KB Output is correct
25 Correct 501 ms 356728 KB Output is correct
26 Correct 501 ms 356728 KB Output is correct
27 Correct 481 ms 356660 KB Output is correct
28 Correct 476 ms 356600 KB Output is correct
29 Correct 483 ms 356692 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 356728 KB Output is correct
2 Correct 487 ms 356692 KB Output is correct
3 Correct 484 ms 356728 KB Output is correct
4 Correct 485 ms 356728 KB Output is correct
5 Correct 494 ms 356700 KB Output is correct
6 Correct 492 ms 356692 KB Output is correct
7 Correct 481 ms 356728 KB Output is correct
8 Correct 488 ms 356736 KB Output is correct
9 Correct 486 ms 356732 KB Output is correct
10 Correct 594 ms 356856 KB Output is correct
11 Correct 498 ms 356700 KB Output is correct
12 Correct 519 ms 356764 KB Output is correct
13 Correct 505 ms 356728 KB Output is correct
14 Correct 481 ms 356600 KB Output is correct
15 Correct 480 ms 356600 KB Output is correct
16 Correct 488 ms 356572 KB Output is correct
17 Correct 485 ms 357232 KB Output is correct
18 Correct 483 ms 357080 KB Output is correct
19 Correct 490 ms 357240 KB Output is correct
20 Correct 489 ms 356908 KB Output is correct
21 Correct 494 ms 356956 KB Output is correct
22 Correct 488 ms 356956 KB Output is correct
23 Correct 482 ms 356936 KB Output is correct
24 Correct 517 ms 356984 KB Output is correct
25 Correct 499 ms 359344 KB Output is correct
26 Correct 505 ms 359520 KB Output is correct
27 Correct 514 ms 359416 KB Output is correct
28 Correct 489 ms 357880 KB Output is correct
29 Correct 499 ms 358408 KB Output is correct
30 Incorrect 515 ms 358364 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 356728 KB Output is correct
2 Correct 487 ms 356692 KB Output is correct
3 Correct 484 ms 356728 KB Output is correct
4 Correct 485 ms 356728 KB Output is correct
5 Correct 494 ms 356700 KB Output is correct
6 Correct 492 ms 356692 KB Output is correct
7 Correct 481 ms 356728 KB Output is correct
8 Correct 488 ms 356736 KB Output is correct
9 Correct 486 ms 356732 KB Output is correct
10 Correct 594 ms 356856 KB Output is correct
11 Correct 498 ms 356700 KB Output is correct
12 Correct 519 ms 356764 KB Output is correct
13 Correct 505 ms 356728 KB Output is correct
14 Correct 481 ms 356600 KB Output is correct
15 Correct 480 ms 356600 KB Output is correct
16 Correct 488 ms 356572 KB Output is correct
17 Correct 485 ms 357232 KB Output is correct
18 Correct 483 ms 357080 KB Output is correct
19 Correct 490 ms 357240 KB Output is correct
20 Correct 489 ms 356908 KB Output is correct
21 Correct 494 ms 356956 KB Output is correct
22 Correct 488 ms 356956 KB Output is correct
23 Correct 482 ms 356936 KB Output is correct
24 Correct 517 ms 356984 KB Output is correct
25 Correct 499 ms 359344 KB Output is correct
26 Correct 505 ms 359520 KB Output is correct
27 Correct 514 ms 359416 KB Output is correct
28 Correct 489 ms 357880 KB Output is correct
29 Correct 499 ms 358408 KB Output is correct
30 Incorrect 515 ms 358364 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 356988 KB Output is correct
2 Correct 491 ms 356984 KB Output is correct
3 Correct 483 ms 356984 KB Output is correct
4 Correct 478 ms 356600 KB Output is correct
5 Correct 487 ms 356984 KB Output is correct
6 Correct 487 ms 356984 KB Output is correct
7 Correct 487 ms 356928 KB Output is correct
8 Correct 484 ms 356856 KB Output is correct
9 Correct 483 ms 356856 KB Output is correct
10 Correct 485 ms 356820 KB Output is correct
11 Correct 532 ms 356824 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 356572 KB Output is correct
2 Correct 1126 ms 424224 KB Output is correct
3 Correct 1985 ms 503324 KB Output is correct
4 Correct 1860 ms 504172 KB Output is correct
5 Correct 2040 ms 504292 KB Output is correct
6 Correct 619 ms 380904 KB Output is correct
7 Correct 767 ms 402872 KB Output is correct
8 Correct 740 ms 406040 KB Output is correct
9 Correct 501 ms 356728 KB Output is correct
10 Correct 501 ms 356728 KB Output is correct
11 Correct 481 ms 356660 KB Output is correct
12 Correct 476 ms 356600 KB Output is correct
13 Correct 483 ms 356692 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 356728 KB Output is correct
2 Correct 487 ms 356692 KB Output is correct
3 Correct 484 ms 356728 KB Output is correct
4 Correct 485 ms 356728 KB Output is correct
5 Correct 494 ms 356700 KB Output is correct
6 Correct 492 ms 356692 KB Output is correct
7 Correct 481 ms 356728 KB Output is correct
8 Correct 488 ms 356736 KB Output is correct
9 Correct 486 ms 356732 KB Output is correct
10 Correct 594 ms 356856 KB Output is correct
11 Correct 498 ms 356700 KB Output is correct
12 Correct 519 ms 356764 KB Output is correct
13 Correct 505 ms 356728 KB Output is correct
14 Correct 481 ms 356600 KB Output is correct
15 Correct 480 ms 356600 KB Output is correct
16 Correct 488 ms 356572 KB Output is correct
17 Correct 485 ms 357232 KB Output is correct
18 Correct 483 ms 357080 KB Output is correct
19 Correct 490 ms 357240 KB Output is correct
20 Correct 489 ms 356908 KB Output is correct
21 Correct 494 ms 356956 KB Output is correct
22 Correct 488 ms 356956 KB Output is correct
23 Correct 482 ms 356936 KB Output is correct
24 Correct 517 ms 356984 KB Output is correct
25 Correct 499 ms 359344 KB Output is correct
26 Correct 505 ms 359520 KB Output is correct
27 Correct 514 ms 359416 KB Output is correct
28 Correct 489 ms 357880 KB Output is correct
29 Correct 499 ms 358408 KB Output is correct
30 Incorrect 515 ms 358364 KB Output isn't correct
31 Halted 0 ms 0 KB -