oj.uz

Submission #144032

# Submission time Handle Problem Language Result Execution time Memory
144032 2019-08-15T17:44:17 Z Kanon Rectangles (IOI19_rect) C++14
72 / 100
 3116 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);
    }
  }
  a.clear();
  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 535 ms 589708 KB Output is correct
2 Correct 569 ms 589816 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 538 ms 589960 KB Output is correct
5 Correct 538 ms 589816 KB Output is correct
6 Correct 535 ms 589944 KB Output is correct
7 Correct 535 ms 589948 KB Output is correct
8 Correct 537 ms 589820 KB Output is correct
9 Correct 537 ms 589940 KB Output is correct
10 Correct 539 ms 589944 KB Output is correct
11 Correct 540 ms 589816 KB Output is correct
12 Correct 531 ms 589856 KB Output is correct
13 Correct 535 ms 589812 KB Output is correct
14 Correct 538 ms 589788 KB Output is correct
15 Correct 545 ms 589820 KB Output is correct
16 Correct 540 ms 589756 KB Output is correct
17 Correct 540 ms 589776 KB Output is correct
18 Correct 572 ms 589800 KB Output is correct
19 Correct 561 ms 589784 KB Output is correct
20 Correct 541 ms 589868 KB Output is correct
21 Correct 540 ms 589816 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 589708 KB Output is correct
2 Correct 569 ms 589816 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 538 ms 589960 KB Output is correct
5 Correct 538 ms 589816 KB Output is correct
6 Correct 535 ms 589944 KB Output is correct
7 Correct 535 ms 589948 KB Output is correct
8 Correct 537 ms 589820 KB Output is correct
9 Correct 537 ms 589940 KB Output is correct
10 Correct 539 ms 589944 KB Output is correct
11 Correct 540 ms 589816 KB Output is correct
12 Correct 531 ms 589856 KB Output is correct
13 Correct 535 ms 589812 KB Output is correct
14 Correct 538 ms 589788 KB Output is correct
15 Correct 545 ms 589820 KB Output is correct
16 Correct 540 ms 589756 KB Output is correct
17 Correct 551 ms 590332 KB Output is correct
18 Correct 558 ms 590348 KB Output is correct
19 Correct 551 ms 590432 KB Output is correct
20 Correct 551 ms 590144 KB Output is correct
21 Correct 562 ms 590360 KB Output is correct
22 Correct 555 ms 590384 KB Output is correct
23 Correct 578 ms 590336 KB Output is correct
24 Correct 545 ms 590172 KB Output is correct
25 Correct 540 ms 589776 KB Output is correct
26 Correct 572 ms 589800 KB Output is correct
27 Correct 561 ms 589784 KB Output is correct
28 Correct 541 ms 589868 KB Output is correct
29 Correct 540 ms 589816 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 589708 KB Output is correct
2 Correct 569 ms 589816 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 538 ms 589960 KB Output is correct
5 Correct 538 ms 589816 KB Output is correct
6 Correct 535 ms 589944 KB Output is correct
7 Correct 535 ms 589948 KB Output is correct
8 Correct 537 ms 589820 KB Output is correct
9 Correct 537 ms 589940 KB Output is correct
10 Correct 539 ms 589944 KB Output is correct
11 Correct 540 ms 589816 KB Output is correct
12 Correct 531 ms 589856 KB Output is correct
13 Correct 535 ms 589812 KB Output is correct
14 Correct 538 ms 589788 KB Output is correct
15 Correct 545 ms 589820 KB Output is correct
16 Correct 540 ms 589756 KB Output is correct
17 Correct 551 ms 590332 KB Output is correct
18 Correct 558 ms 590348 KB Output is correct
19 Correct 551 ms 590432 KB Output is correct
20 Correct 551 ms 590144 KB Output is correct
21 Correct 562 ms 590360 KB Output is correct
22 Correct 555 ms 590384 KB Output is correct
23 Correct 578 ms 590336 KB Output is correct
24 Correct 545 ms 590172 KB Output is correct
25 Correct 581 ms 593932 KB Output is correct
26 Correct 585 ms 593840 KB Output is correct
27 Correct 561 ms 593920 KB Output is correct
28 Correct 546 ms 591616 KB Output is correct
29 Correct 571 ms 593756 KB Output is correct
30 Correct 564 ms 593712 KB Output is correct
31 Correct 557 ms 593400 KB Output is correct
32 Correct 568 ms 593500 KB Output is correct
33 Correct 540 ms 589776 KB Output is correct
34 Correct 572 ms 589800 KB Output is correct
35 Correct 561 ms 589784 KB Output is correct
36 Correct 541 ms 589868 KB Output is correct
37 Correct 540 ms 589816 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 589708 KB Output is correct
2 Correct 569 ms 589816 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 538 ms 589960 KB Output is correct
5 Correct 538 ms 589816 KB Output is correct
6 Correct 535 ms 589944 KB Output is correct
7 Correct 535 ms 589948 KB Output is correct
8 Correct 537 ms 589820 KB Output is correct
9 Correct 537 ms 589940 KB Output is correct
10 Correct 539 ms 589944 KB Output is correct
11 Correct 540 ms 589816 KB Output is correct
12 Correct 531 ms 589856 KB Output is correct
13 Correct 535 ms 589812 KB Output is correct
14 Correct 538 ms 589788 KB Output is correct
15 Correct 545 ms 589820 KB Output is correct
16 Correct 540 ms 589756 KB Output is correct
17 Correct 551 ms 590332 KB Output is correct
18 Correct 558 ms 590348 KB Output is correct
19 Correct 551 ms 590432 KB Output is correct
20 Correct 551 ms 590144 KB Output is correct
21 Correct 562 ms 590360 KB Output is correct
22 Correct 555 ms 590384 KB Output is correct
23 Correct 578 ms 590336 KB Output is correct
24 Correct 545 ms 590172 KB Output is correct
25 Correct 581 ms 593932 KB Output is correct
26 Correct 585 ms 593840 KB Output is correct
27 Correct 561 ms 593920 KB Output is correct
28 Correct 546 ms 591616 KB Output is correct
29 Correct 571 ms 593756 KB Output is correct
30 Correct 564 ms 593712 KB Output is correct
31 Correct 557 ms 593400 KB Output is correct
32 Correct 568 ms 593500 KB Output is correct
33 Correct 807 ms 616724 KB Output is correct
34 Correct 719 ms 616696 KB Output is correct
35 Correct 703 ms 616648 KB Output is correct
36 Correct 685 ms 616712 KB Output is correct
37 Correct 903 ms 639704 KB Output is correct
38 Correct 964 ms 639556 KB Output is correct
39 Correct 908 ms 639700 KB Output is correct
40 Correct 880 ms 636392 KB Output is correct
41 Correct 696 ms 605120 KB Output is correct
42 Correct 682 ms 611496 KB Output is correct
43 Correct 836 ms 638456 KB Output is correct
44 Correct 841 ms 638928 KB Output is correct
45 Correct 689 ms 614352 KB Output is correct
46 Correct 688 ms 614264 KB Output is correct
47 Correct 822 ms 635128 KB Output is correct
48 Correct 910 ms 635344 KB Output is correct
49 Correct 540 ms 589776 KB Output is correct
50 Correct 572 ms 589800 KB Output is correct
51 Correct 561 ms 589784 KB Output is correct
52 Correct 541 ms 589868 KB Output is correct
53 Correct 540 ms 589816 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 590352 KB Output is correct
2 Correct 540 ms 590208 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 540 ms 589688 KB Output is correct
5 Correct 545 ms 590196 KB Output is correct
6 Correct 548 ms 590200 KB Output is correct
7 Correct 540 ms 590240 KB Output is correct
8 Correct 541 ms 590328 KB Output is correct
9 Correct 577 ms 590304 KB Output is correct
10 Correct 547 ms 589980 KB Output is correct
11 Correct 552 ms 590112 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 589772 KB Output is correct
2 Correct 1192 ms 679588 KB Output is correct
3 Correct 2087 ms 784576 KB Output is correct
4 Correct 2052 ms 785652 KB Output is correct
5 Correct 2063 ms 785544 KB Output is correct
6 Correct 758 ms 614136 KB Output is correct
7 Correct 934 ms 635896 KB Output is correct
8 Correct 1006 ms 638968 KB Output is correct
9 Correct 540 ms 589776 KB Output is correct
10 Correct 572 ms 589800 KB Output is correct
11 Correct 561 ms 589784 KB Output is correct
12 Correct 541 ms 589868 KB Output is correct
13 Correct 540 ms 589816 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 589708 KB Output is correct
2 Correct 569 ms 589816 KB Output is correct
3 Correct 536 ms 589944 KB Output is correct
4 Correct 538 ms 589960 KB Output is correct
5 Correct 538 ms 589816 KB Output is correct
6 Correct 535 ms 589944 KB Output is correct
7 Correct 535 ms 589948 KB Output is correct
8 Correct 537 ms 589820 KB Output is correct
9 Correct 537 ms 589940 KB Output is correct
10 Correct 539 ms 589944 KB Output is correct
11 Correct 540 ms 589816 KB Output is correct
12 Correct 531 ms 589856 KB Output is correct
13 Correct 535 ms 589812 KB Output is correct
14 Correct 538 ms 589788 KB Output is correct
15 Correct 545 ms 589820 KB Output is correct
16 Correct 540 ms 589756 KB Output is correct
17 Correct 551 ms 590332 KB Output is correct
18 Correct 558 ms 590348 KB Output is correct
19 Correct 551 ms 590432 KB Output is correct
20 Correct 551 ms 590144 KB Output is correct
21 Correct 562 ms 590360 KB Output is correct
22 Correct 555 ms 590384 KB Output is correct
23 Correct 578 ms 590336 KB Output is correct
24 Correct 545 ms 590172 KB Output is correct
25 Correct 581 ms 593932 KB Output is correct
26 Correct 585 ms 593840 KB Output is correct
27 Correct 561 ms 593920 KB Output is correct
28 Correct 546 ms 591616 KB Output is correct
29 Correct 571 ms 593756 KB Output is correct
30 Correct 564 ms 593712 KB Output is correct
31 Correct 557 ms 593400 KB Output is correct
32 Correct 568 ms 593500 KB Output is correct
33 Correct 807 ms 616724 KB Output is correct
34 Correct 719 ms 616696 KB Output is correct
35 Correct 703 ms 616648 KB Output is correct
36 Correct 685 ms 616712 KB Output is correct
37 Correct 903 ms 639704 KB Output is correct
38 Correct 964 ms 639556 KB Output is correct
39 Correct 908 ms 639700 KB Output is correct
40 Correct 880 ms 636392 KB Output is correct
41 Correct 696 ms 605120 KB Output is correct
42 Correct 682 ms 611496 KB Output is correct
43 Correct 836 ms 638456 KB Output is correct
44 Correct 841 ms 638928 KB Output is correct
45 Correct 689 ms 614352 KB Output is correct
46 Correct 688 ms 614264 KB Output is correct
47 Correct 822 ms 635128 KB Output is correct
48 Correct 910 ms 635344 KB Output is correct
49 Correct 542 ms 590352 KB Output is correct
50 Correct 540 ms 590208 KB Output is correct
51 Correct 536 ms 589944 KB Output is correct
52 Correct 540 ms 589688 KB Output is correct
53 Correct 545 ms 590196 KB Output is correct
54 Correct 548 ms 590200 KB Output is correct
55 Correct 540 ms 590240 KB Output is correct
56 Correct 541 ms 590328 KB Output is correct
57 Correct 577 ms 590304 KB Output is correct
58 Correct 547 ms 589980 KB Output is correct
59 Correct 552 ms 590112 KB Output is correct
60 Correct 599 ms 589772 KB Output is correct
61 Correct 1192 ms 679588 KB Output is correct
62 Correct 2087 ms 784576 KB Output is correct
63 Correct 2052 ms 785652 KB Output is correct
64 Correct 2063 ms 785544 KB Output is correct
65 Correct 758 ms 614136 KB Output is correct
66 Correct 934 ms 635896 KB Output is correct
67 Correct 1006 ms 638968 KB Output is correct
68 Correct 2918 ms 932364 KB Output is correct
69 Correct 2691 ms 932452 KB Output is correct
70 Correct 2832 ms 932344 KB Output is correct
71 Correct 2562 ms 932572 KB Output is correct
72 Runtime error 3116 ms 1048580 KB Execution killed with signal 9 (could be triggered by violating memory limits)
73 Halted 0 ms 0 KB -