oj.uz

Submission #144030

# Submission time Handle Problem Language Result Execution time Memory
144030 2019-08-15T17:39:43 Z Kanon Rectangles (IOI19_rect) C++14
72 / 100
 3132 ms 1048580 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<long long, null_type, greater<long long>, rb_tree_tag,tree_order_statistics_node_update>
#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

const int N = 2505;

set<pair<short, short>> hp[N][N], vs[N][N];

long long count_rectangles(vector<vector<int>> a) {
  int m = a.front().size();
  int n = a.size();
  auto pos = [&] (vector<int> cur) {
    int s = cur.size();
    vector<pair<int, int>> res;
    vector<int> st;
    range(i, 0, s) {
      while(st.size() && cur[st.back()] <= cur[i]) {
        if(st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
        int b = st.back();
        st.pop_back();
        if(cur[b] == cur[i]) goto A;
      }
      if(st.size() && st.back() < i - 1) res.emplace_back(st.back() + 1, i - 1);
      A:;
      st.push_back(i);
    }
    return res;
  };
  range(i, 0, n) {
    vector<pair<int, int>> foo = pos(a[i]);
    for(auto u : foo) {
      int l = u.first, r = u.second;
      pair<short, short> p = make_pair(l, i);
      if(i && hp[i - 1][r].lower_bound(make_pair(l, -1))->first == l) p.second = hp[i - 1][r].lower_bound(make_pair(l, -1))->second;
      hp[i][r].insert(p);
    }
  }
  range(i, 0, m) {
    vector<int> ss(n);
    range(j, 0, n) ss[j] = a[j][i];
    vector<pair<int, int>> foo = pos(ss);
    for(auto u : foo) {
      int l = u.first, r = u.second;
      pair<short, short> p = make_pair(l, i);
      if(i && vs[r][i - 1].lower_bound(make_pair(l, -1))->first == l) p.second = vs[r][i - 1].lower_bound(make_pair(l, -1))->second;
      vs[r][i].insert(p);
    }
  }
  long long res = 0;
  auto cnt = [&](set<pair<short, short>> &x, set<pair<short, short>> &y) {
    vector<pair<int, int>> sy;
    for(auto i : y) {
      swap(i.first, i.second);
      sy.push_back(i);
    }
    sort(sy.begin(), sy.end());
    reverse(sy.begin(), sy.end());
    ordered_set cur;
    auto it = x.begin();
    int p = sy.size() - 1;
    while(it != x.end()) {
      while(~p && sy[p].first <= it->first) {
        cur.insert(sy[p].second);
        p--;
      }
      res += cur.order_of_key(it->second - 1);
      it++;
    }
  };
  range(i, 0, n) {
    range(j, 0, m) {
      cnt(hp[i][j], vs[i][j]);
    }
  }
  return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 589784 KB Output is correct
2 Correct 538 ms 589944 KB Output is correct
3 Correct 537 ms 590084 KB Output is correct
4 Correct 545 ms 589944 KB Output is correct
5 Correct 541 ms 589816 KB Output is correct
6 Correct 537 ms 589852 KB Output is correct
7 Correct 537 ms 590076 KB Output is correct
8 Correct 537 ms 589944 KB Output is correct
9 Correct 537 ms 589944 KB Output is correct
10 Correct 537 ms 589912 KB Output is correct
11 Correct 537 ms 589744 KB Output is correct
12 Correct 537 ms 589992 KB Output is correct
13 Correct 534 ms 589816 KB Output is correct
14 Correct 540 ms 589716 KB Output is correct
15 Correct 551 ms 589904 KB Output is correct
16 Correct 589 ms 589944 KB Output is correct
17 Correct 537 ms 589924 KB Output is correct
18 Correct 540 ms 589848 KB Output is correct
19 Correct 541 ms 589912 KB Output is correct
20 Correct 535 ms 589772 KB Output is correct
21 Correct 535 ms 589788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 589784 KB Output is correct
2 Correct 538 ms 589944 KB Output is correct
3 Correct 537 ms 590084 KB Output is correct
4 Correct 545 ms 589944 KB Output is correct
5 Correct 541 ms 589816 KB Output is correct
6 Correct 537 ms 589852 KB Output is correct
7 Correct 537 ms 590076 KB Output is correct
8 Correct 537 ms 589944 KB Output is correct
9 Correct 537 ms 589944 KB Output is correct
10 Correct 537 ms 589912 KB Output is correct
11 Correct 537 ms 589744 KB Output is correct
12 Correct 537 ms 589992 KB Output is correct
13 Correct 534 ms 589816 KB Output is correct
14 Correct 540 ms 589716 KB Output is correct
15 Correct 551 ms 589904 KB Output is correct
16 Correct 589 ms 589944 KB Output is correct
17 Correct 546 ms 590384 KB Output is correct
18 Correct 554 ms 590416 KB Output is correct
19 Correct 540 ms 590540 KB Output is correct
20 Correct 540 ms 590072 KB Output is correct
21 Correct 540 ms 590364 KB Output is correct
22 Correct 537 ms 590328 KB Output is correct
23 Correct 537 ms 590360 KB Output is correct
24 Correct 537 ms 590200 KB Output is correct
25 Correct 537 ms 589924 KB Output is correct
26 Correct 540 ms 589848 KB Output is correct
27 Correct 541 ms 589912 KB Output is correct
28 Correct 535 ms 589772 KB Output is correct
29 Correct 535 ms 589788 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 589784 KB Output is correct
2 Correct 538 ms 589944 KB Output is correct
3 Correct 537 ms 590084 KB Output is correct
4 Correct 545 ms 589944 KB Output is correct
5 Correct 541 ms 589816 KB Output is correct
6 Correct 537 ms 589852 KB Output is correct
7 Correct 537 ms 590076 KB Output is correct
8 Correct 537 ms 589944 KB Output is correct
9 Correct 537 ms 589944 KB Output is correct
10 Correct 537 ms 589912 KB Output is correct
11 Correct 537 ms 589744 KB Output is correct
12 Correct 537 ms 589992 KB Output is correct
13 Correct 534 ms 589816 KB Output is correct
14 Correct 540 ms 589716 KB Output is correct
15 Correct 551 ms 589904 KB Output is correct
16 Correct 589 ms 589944 KB Output is correct
17 Correct 546 ms 590384 KB Output is correct
18 Correct 554 ms 590416 KB Output is correct
19 Correct 540 ms 590540 KB Output is correct
20 Correct 540 ms 590072 KB Output is correct
21 Correct 540 ms 590364 KB Output is correct
22 Correct 537 ms 590328 KB Output is correct
23 Correct 537 ms 590360 KB Output is correct
24 Correct 537 ms 590200 KB Output is correct
25 Correct 561 ms 593784 KB Output is correct
26 Correct 554 ms 593972 KB Output is correct
27 Correct 564 ms 593828 KB Output is correct
28 Correct 547 ms 591600 KB Output is correct
29 Correct 636 ms 593588 KB Output is correct
30 Correct 563 ms 593656 KB Output is correct
31 Correct 561 ms 593444 KB Output is correct
32 Correct 593 ms 593528 KB Output is correct
33 Correct 537 ms 589924 KB Output is correct
34 Correct 540 ms 589848 KB Output is correct
35 Correct 541 ms 589912 KB Output is correct
36 Correct 535 ms 589772 KB Output is correct
37 Correct 535 ms 589788 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 589784 KB Output is correct
2 Correct 538 ms 589944 KB Output is correct
3 Correct 537 ms 590084 KB Output is correct
4 Correct 545 ms 589944 KB Output is correct
5 Correct 541 ms 589816 KB Output is correct
6 Correct 537 ms 589852 KB Output is correct
7 Correct 537 ms 590076 KB Output is correct
8 Correct 537 ms 589944 KB Output is correct
9 Correct 537 ms 589944 KB Output is correct
10 Correct 537 ms 589912 KB Output is correct
11 Correct 537 ms 589744 KB Output is correct
12 Correct 537 ms 589992 KB Output is correct
13 Correct 534 ms 589816 KB Output is correct
14 Correct 540 ms 589716 KB Output is correct
15 Correct 551 ms 589904 KB Output is correct
16 Correct 589 ms 589944 KB Output is correct
17 Correct 546 ms 590384 KB Output is correct
18 Correct 554 ms 590416 KB Output is correct
19 Correct 540 ms 590540 KB Output is correct
20 Correct 540 ms 590072 KB Output is correct
21 Correct 540 ms 590364 KB Output is correct
22 Correct 537 ms 590328 KB Output is correct
23 Correct 537 ms 590360 KB Output is correct
24 Correct 537 ms 590200 KB Output is correct
25 Correct 561 ms 593784 KB Output is correct
26 Correct 554 ms 593972 KB Output is correct
27 Correct 564 ms 593828 KB Output is correct
28 Correct 547 ms 591600 KB Output is correct
29 Correct 636 ms 593588 KB Output is correct
30 Correct 563 ms 593656 KB Output is correct
31 Correct 561 ms 593444 KB Output is correct
32 Correct 593 ms 593528 KB Output is correct
33 Correct 707 ms 616644 KB Output is correct
34 Correct 693 ms 616568 KB Output is correct
35 Correct 700 ms 616712 KB Output is correct
36 Correct 678 ms 616668 KB Output is correct
37 Correct 926 ms 639616 KB Output is correct
38 Correct 897 ms 639612 KB Output is correct
39 Correct 916 ms 639748 KB Output is correct
40 Correct 872 ms 636504 KB Output is correct
41 Correct 659 ms 605072 KB Output is correct
42 Correct 690 ms 611576 KB Output is correct
43 Correct 844 ms 638348 KB Output is correct
44 Correct 881 ms 638924 KB Output is correct
45 Correct 693 ms 614308 KB Output is correct
46 Correct 701 ms 614264 KB Output is correct
47 Correct 841 ms 635248 KB Output is correct
48 Correct 840 ms 635356 KB Output is correct
49 Correct 537 ms 589924 KB Output is correct
50 Correct 540 ms 589848 KB Output is correct
51 Correct 541 ms 589912 KB Output is correct
52 Correct 535 ms 589772 KB Output is correct
53 Correct 535 ms 589788 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 590376 KB Output is correct
2 Correct 540 ms 590200 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 586 ms 589964 KB Output is correct
5 Correct 542 ms 590200 KB Output is correct
6 Correct 553 ms 590184 KB Output is correct
7 Correct 548 ms 590328 KB Output is correct
8 Correct 541 ms 590284 KB Output is correct
9 Correct 540 ms 590204 KB Output is correct
10 Correct 562 ms 590072 KB Output is correct
11 Correct 550 ms 590132 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 589812 KB Output is correct
2 Correct 1227 ms 679600 KB Output is correct
3 Correct 2220 ms 784344 KB Output is correct
4 Correct 2143 ms 785404 KB Output is correct
5 Correct 2102 ms 785564 KB Output is correct
6 Correct 725 ms 614192 KB Output is correct
7 Correct 923 ms 635896 KB Output is correct
8 Correct 967 ms 638916 KB Output is correct
9 Correct 537 ms 589924 KB Output is correct
10 Correct 540 ms 589848 KB Output is correct
11 Correct 541 ms 589912 KB Output is correct
12 Correct 535 ms 589772 KB Output is correct
13 Correct 535 ms 589788 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 589784 KB Output is correct
2 Correct 538 ms 589944 KB Output is correct
3 Correct 537 ms 590084 KB Output is correct
4 Correct 545 ms 589944 KB Output is correct
5 Correct 541 ms 589816 KB Output is correct
6 Correct 537 ms 589852 KB Output is correct
7 Correct 537 ms 590076 KB Output is correct
8 Correct 537 ms 589944 KB Output is correct
9 Correct 537 ms 589944 KB Output is correct
10 Correct 537 ms 589912 KB Output is correct
11 Correct 537 ms 589744 KB Output is correct
12 Correct 537 ms 589992 KB Output is correct
13 Correct 534 ms 589816 KB Output is correct
14 Correct 540 ms 589716 KB Output is correct
15 Correct 551 ms 589904 KB Output is correct
16 Correct 589 ms 589944 KB Output is correct
17 Correct 546 ms 590384 KB Output is correct
18 Correct 554 ms 590416 KB Output is correct
19 Correct 540 ms 590540 KB Output is correct
20 Correct 540 ms 590072 KB Output is correct
21 Correct 540 ms 590364 KB Output is correct
22 Correct 537 ms 590328 KB Output is correct
23 Correct 537 ms 590360 KB Output is correct
24 Correct 537 ms 590200 KB Output is correct
25 Correct 561 ms 593784 KB Output is correct
26 Correct 554 ms 593972 KB Output is correct
27 Correct 564 ms 593828 KB Output is correct
28 Correct 547 ms 591600 KB Output is correct
29 Correct 636 ms 593588 KB Output is correct
30 Correct 563 ms 593656 KB Output is correct
31 Correct 561 ms 593444 KB Output is correct
32 Correct 593 ms 593528 KB Output is correct
33 Correct 707 ms 616644 KB Output is correct
34 Correct 693 ms 616568 KB Output is correct
35 Correct 700 ms 616712 KB Output is correct
36 Correct 678 ms 616668 KB Output is correct
37 Correct 926 ms 639616 KB Output is correct
38 Correct 897 ms 639612 KB Output is correct
39 Correct 916 ms 639748 KB Output is correct
40 Correct 872 ms 636504 KB Output is correct
41 Correct 659 ms 605072 KB Output is correct
42 Correct 690 ms 611576 KB Output is correct
43 Correct 844 ms 638348 KB Output is correct
44 Correct 881 ms 638924 KB Output is correct
45 Correct 693 ms 614308 KB Output is correct
46 Correct 701 ms 614264 KB Output is correct
47 Correct 841 ms 635248 KB Output is correct
48 Correct 840 ms 635356 KB Output is correct
49 Correct 541 ms 590376 KB Output is correct
50 Correct 540 ms 590200 KB Output is correct
51 Correct 536 ms 589944 KB Output is correct
52 Correct 586 ms 589964 KB Output is correct
53 Correct 542 ms 590200 KB Output is correct
54 Correct 553 ms 590184 KB Output is correct
55 Correct 548 ms 590328 KB Output is correct
56 Correct 541 ms 590284 KB Output is correct
57 Correct 540 ms 590204 KB Output is correct
58 Correct 562 ms 590072 KB Output is correct
59 Correct 550 ms 590132 KB Output is correct
60 Correct 536 ms 589812 KB Output is correct
61 Correct 1227 ms 679600 KB Output is correct
62 Correct 2220 ms 784344 KB Output is correct
63 Correct 2143 ms 785404 KB Output is correct
64 Correct 2102 ms 785564 KB Output is correct
65 Correct 725 ms 614192 KB Output is correct
66 Correct 923 ms 635896 KB Output is correct
67 Correct 967 ms 638916 KB Output is correct
68 Correct 2974 ms 932584 KB Output is correct
69 Correct 2768 ms 932516 KB Output is correct
70 Correct 2860 ms 932308 KB Output is correct
71 Correct 2494 ms 932368 KB Output is correct
72 Runtime error 3132 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Halted 0 ms 0 KB -