oj.uz

Submission #143544

# Submission time Handle Problem Language Result Execution time Memory
143544 2019-08-14T14:25:43 Z icypiggy Rectangles (IOI19_rect) C++14
72 / 100
 5000 ms 758000 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>> v_map2[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());
        }
    }

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

    return ans;
}

Compilation message

rect.cpp: In function 'void gen_h_seg(std::vector<int>&, int)':
rect.cpp:16: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:65: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:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:91:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:97:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a[0].size(); j++) {
                      ~^~~~~~~~~~~~
rect.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:109:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0; j<a[0].size(); j++) {
                  ~^~~~~~~~~~~~
rect.cpp:111:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<a.size(); i++) {
                      ~^~~~~~~~~
rect.cpp:115:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(down+1!=a.size()) {
                           ~~~~~~^~~~~~~~~~
rect.cpp:136:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(down+1!=a[0].size()) {
                           ~~~~~~^~~~~~~~~~~~~
rect.cpp:151:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int a=0; a<v_map2[i].size(); a++) {
                          ~^~~~~~~~~~~~~~~~~
rect.cpp:152: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 274 ms 305912 KB Output is correct
2 Correct 291 ms 306168 KB Output is correct
3 Correct 309 ms 306168 KB Output is correct
4 Correct 275 ms 306204 KB Output is correct
5 Correct 315 ms 305784 KB Output is correct
6 Correct 277 ms 306168 KB Output is correct
7 Correct 274 ms 306168 KB Output is correct
8 Correct 292 ms 306044 KB Output is correct
9 Correct 277 ms 306040 KB Output is correct
10 Correct 283 ms 306040 KB Output is correct
11 Correct 277 ms 306036 KB Output is correct
12 Correct 276 ms 306220 KB Output is correct
13 Correct 273 ms 305820 KB Output is correct
14 Correct 274 ms 305836 KB Output is correct
15 Correct 281 ms 305912 KB Output is correct
16 Correct 275 ms 305784 KB Output is correct
17 Correct 275 ms 305784 KB Output is correct
18 Correct 275 ms 305784 KB Output is correct
19 Correct 286 ms 306028 KB Output is correct
20 Correct 274 ms 305784 KB Output is correct
21 Correct 338 ms 305784 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 305912 KB Output is correct
2 Correct 291 ms 306168 KB Output is correct
3 Correct 309 ms 306168 KB Output is correct
4 Correct 275 ms 306204 KB Output is correct
5 Correct 315 ms 305784 KB Output is correct
6 Correct 277 ms 306168 KB Output is correct
7 Correct 274 ms 306168 KB Output is correct
8 Correct 292 ms 306044 KB Output is correct
9 Correct 277 ms 306040 KB Output is correct
10 Correct 283 ms 306040 KB Output is correct
11 Correct 277 ms 306036 KB Output is correct
12 Correct 276 ms 306220 KB Output is correct
13 Correct 273 ms 305820 KB Output is correct
14 Correct 274 ms 305836 KB Output is correct
15 Correct 281 ms 305912 KB Output is correct
16 Correct 275 ms 305784 KB Output is correct
17 Correct 277 ms 306964 KB Output is correct
18 Correct 281 ms 307064 KB Output is correct
19 Correct 278 ms 307064 KB Output is correct
20 Correct 278 ms 306936 KB Output is correct
21 Correct 277 ms 306952 KB Output is correct
22 Correct 281 ms 307004 KB Output is correct
23 Correct 278 ms 306860 KB Output is correct
24 Correct 277 ms 306680 KB Output is correct
25 Correct 275 ms 305784 KB Output is correct
26 Correct 275 ms 305784 KB Output is correct
27 Correct 286 ms 306028 KB Output is correct
28 Correct 274 ms 305784 KB Output is correct
29 Correct 338 ms 305784 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 305912 KB Output is correct
2 Correct 291 ms 306168 KB Output is correct
3 Correct 309 ms 306168 KB Output is correct
4 Correct 275 ms 306204 KB Output is correct
5 Correct 315 ms 305784 KB Output is correct
6 Correct 277 ms 306168 KB Output is correct
7 Correct 274 ms 306168 KB Output is correct
8 Correct 292 ms 306044 KB Output is correct
9 Correct 277 ms 306040 KB Output is correct
10 Correct 283 ms 306040 KB Output is correct
11 Correct 277 ms 306036 KB Output is correct
12 Correct 276 ms 306220 KB Output is correct
13 Correct 273 ms 305820 KB Output is correct
14 Correct 274 ms 305836 KB Output is correct
15 Correct 281 ms 305912 KB Output is correct
16 Correct 275 ms 305784 KB Output is correct
17 Correct 277 ms 306964 KB Output is correct
18 Correct 281 ms 307064 KB Output is correct
19 Correct 278 ms 307064 KB Output is correct
20 Correct 278 ms 306936 KB Output is correct
21 Correct 277 ms 306952 KB Output is correct
22 Correct 281 ms 307004 KB Output is correct
23 Correct 278 ms 306860 KB Output is correct
24 Correct 277 ms 306680 KB Output is correct
25 Correct 290 ms 310720 KB Output is correct
26 Correct 292 ms 310624 KB Output is correct
27 Correct 293 ms 310648 KB Output is correct
28 Correct 288 ms 309012 KB Output is correct
29 Correct 295 ms 309624 KB Output is correct
30 Correct 298 ms 309736 KB Output is correct
31 Correct 293 ms 309512 KB Output is correct
32 Correct 297 ms 309496 KB Output is correct
33 Correct 275 ms 305784 KB Output is correct
34 Correct 275 ms 305784 KB Output is correct
35 Correct 286 ms 306028 KB Output is correct
36 Correct 274 ms 305784 KB Output is correct
37 Correct 338 ms 305784 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 305912 KB Output is correct
2 Correct 291 ms 306168 KB Output is correct
3 Correct 309 ms 306168 KB Output is correct
4 Correct 275 ms 306204 KB Output is correct
5 Correct 315 ms 305784 KB Output is correct
6 Correct 277 ms 306168 KB Output is correct
7 Correct 274 ms 306168 KB Output is correct
8 Correct 292 ms 306044 KB Output is correct
9 Correct 277 ms 306040 KB Output is correct
10 Correct 283 ms 306040 KB Output is correct
11 Correct 277 ms 306036 KB Output is correct
12 Correct 276 ms 306220 KB Output is correct
13 Correct 273 ms 305820 KB Output is correct
14 Correct 274 ms 305836 KB Output is correct
15 Correct 281 ms 305912 KB Output is correct
16 Correct 275 ms 305784 KB Output is correct
17 Correct 277 ms 306964 KB Output is correct
18 Correct 281 ms 307064 KB Output is correct
19 Correct 278 ms 307064 KB Output is correct
20 Correct 278 ms 306936 KB Output is correct
21 Correct 277 ms 306952 KB Output is correct
22 Correct 281 ms 307004 KB Output is correct
23 Correct 278 ms 306860 KB Output is correct
24 Correct 277 ms 306680 KB Output is correct
25 Correct 290 ms 310720 KB Output is correct
26 Correct 292 ms 310624 KB Output is correct
27 Correct 293 ms 310648 KB Output is correct
28 Correct 288 ms 309012 KB Output is correct
29 Correct 295 ms 309624 KB Output is correct
30 Correct 298 ms 309736 KB Output is correct
31 Correct 293 ms 309512 KB Output is correct
32 Correct 297 ms 309496 KB Output is correct
33 Correct 417 ms 332028 KB Output is correct
34 Correct 385 ms 327160 KB Output is correct
35 Correct 414 ms 330072 KB Output is correct
36 Correct 369 ms 325212 KB Output is correct
37 Correct 559 ms 347112 KB Output is correct
38 Correct 551 ms 346852 KB Output is correct
39 Correct 561 ms 347128 KB Output is correct
40 Correct 537 ms 344392 KB Output is correct
41 Correct 385 ms 324524 KB Output is correct
42 Correct 426 ms 326984 KB Output is correct
43 Correct 596 ms 334776 KB Output is correct
44 Correct 580 ms 335008 KB Output is correct
45 Correct 451 ms 323920 KB Output is correct
46 Correct 448 ms 320376 KB Output is correct
47 Correct 535 ms 333584 KB Output is correct
48 Correct 527 ms 333532 KB Output is correct
49 Correct 275 ms 305784 KB Output is correct
50 Correct 275 ms 305784 KB Output is correct
51 Correct 286 ms 306028 KB Output is correct
52 Correct 274 ms 305784 KB Output is correct
53 Correct 338 ms 305784 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 306260 KB Output is correct
2 Correct 284 ms 306168 KB Output is correct
3 Correct 285 ms 305880 KB Output is correct
4 Correct 277 ms 305832 KB Output is correct
5 Correct 282 ms 306168 KB Output is correct
6 Correct 278 ms 306088 KB Output is correct
7 Correct 279 ms 306168 KB Output is correct
8 Correct 279 ms 306056 KB Output is correct
9 Correct 277 ms 306168 KB Output is correct
10 Correct 278 ms 305916 KB Output is correct
11 Correct 277 ms 305900 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 305828 KB Output is correct
2 Correct 920 ms 385780 KB Output is correct
3 Correct 1776 ms 477552 KB Output is correct
4 Correct 1732 ms 478356 KB Output is correct
5 Correct 1811 ms 478676 KB Output is correct
6 Correct 555 ms 330200 KB Output is correct
7 Correct 863 ms 352164 KB Output is correct
8 Correct 842 ms 355064 KB Output is correct
9 Correct 275 ms 305784 KB Output is correct
10 Correct 275 ms 305784 KB Output is correct
11 Correct 286 ms 306028 KB Output is correct
12 Correct 274 ms 305784 KB Output is correct
13 Correct 338 ms 305784 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 305912 KB Output is correct
2 Correct 291 ms 306168 KB Output is correct
3 Correct 309 ms 306168 KB Output is correct
4 Correct 275 ms 306204 KB Output is correct
5 Correct 315 ms 305784 KB Output is correct
6 Correct 277 ms 306168 KB Output is correct
7 Correct 274 ms 306168 KB Output is correct
8 Correct 292 ms 306044 KB Output is correct
9 Correct 277 ms 306040 KB Output is correct
10 Correct 283 ms 306040 KB Output is correct
11 Correct 277 ms 306036 KB Output is correct
12 Correct 276 ms 306220 KB Output is correct
13 Correct 273 ms 305820 KB Output is correct
14 Correct 274 ms 305836 KB Output is correct
15 Correct 281 ms 305912 KB Output is correct
16 Correct 275 ms 305784 KB Output is correct
17 Correct 277 ms 306964 KB Output is correct
18 Correct 281 ms 307064 KB Output is correct
19 Correct 278 ms 307064 KB Output is correct
20 Correct 278 ms 306936 KB Output is correct
21 Correct 277 ms 306952 KB Output is correct
22 Correct 281 ms 307004 KB Output is correct
23 Correct 278 ms 306860 KB Output is correct
24 Correct 277 ms 306680 KB Output is correct
25 Correct 290 ms 310720 KB Output is correct
26 Correct 292 ms 310624 KB Output is correct
27 Correct 293 ms 310648 KB Output is correct
28 Correct 288 ms 309012 KB Output is correct
29 Correct 295 ms 309624 KB Output is correct
30 Correct 298 ms 309736 KB Output is correct
31 Correct 293 ms 309512 KB Output is correct
32 Correct 297 ms 309496 KB Output is correct
33 Correct 417 ms 332028 KB Output is correct
34 Correct 385 ms 327160 KB Output is correct
35 Correct 414 ms 330072 KB Output is correct
36 Correct 369 ms 325212 KB Output is correct
37 Correct 559 ms 347112 KB Output is correct
38 Correct 551 ms 346852 KB Output is correct
39 Correct 561 ms 347128 KB Output is correct
40 Correct 537 ms 344392 KB Output is correct
41 Correct 385 ms 324524 KB Output is correct
42 Correct 426 ms 326984 KB Output is correct
43 Correct 596 ms 334776 KB Output is correct
44 Correct 580 ms 335008 KB Output is correct
45 Correct 451 ms 323920 KB Output is correct
46 Correct 448 ms 320376 KB Output is correct
47 Correct 535 ms 333584 KB Output is correct
48 Correct 527 ms 333532 KB Output is correct
49 Correct 279 ms 306260 KB Output is correct
50 Correct 284 ms 306168 KB Output is correct
51 Correct 285 ms 305880 KB Output is correct
52 Correct 277 ms 305832 KB Output is correct
53 Correct 282 ms 306168 KB Output is correct
54 Correct 278 ms 306088 KB Output is correct
55 Correct 279 ms 306168 KB Output is correct
56 Correct 279 ms 306056 KB Output is correct
57 Correct 277 ms 306168 KB Output is correct
58 Correct 278 ms 305916 KB Output is correct
59 Correct 277 ms 305900 KB Output is correct
60 Correct 276 ms 305828 KB Output is correct
61 Correct 920 ms 385780 KB Output is correct
62 Correct 1776 ms 477552 KB Output is correct
63 Correct 1732 ms 478356 KB Output is correct
64 Correct 1811 ms 478676 KB Output is correct
65 Correct 555 ms 330200 KB Output is correct
66 Correct 863 ms 352164 KB Output is correct
67 Correct 842 ms 355064 KB Output is correct
68 Correct 2243 ms 569288 KB Output is correct
69 Correct 1785 ms 504520 KB Output is correct
70 Correct 2016 ms 532444 KB Output is correct
71 Correct 1490 ms 467808 KB Output is correct
72 Execution timed out 5128 ms 758000 KB Time limit exceeded
73 Halted 0 ms 0 KB -