Submission #762831

# Submission time Handle Problem Language Result Execution time Memory
762831 2023-06-21T20:37:12 Z caganyanmaz Pairs (IOI07_pairs) C++17
52 / 100
2741 ms 524288 KB
#include <bits/stdc++.h>
#define int int64_t
#define pb push_back
using namespace std;


struct SegTree1d
{
        int n;
        vector<int> data, left, right;
        SegTree1d(int n) : n(n), data(1, 0), left(1, -1), right(1, -1) {}
        void cc(int index)
        {
                if (left[index] == -1)
                {
                        left[index] = data.size();
                        data.pb(0);
                        left.pb(-1);
                        right.pb(-1);
                }
                if (right[index] == -1)
                {
                        right[index] = data.size();
                        data.pb(0);
                        left.pb(-1);
                        right.pb(-1);
                }
        }
        void update(int l, int r, int index, int i, int val)
        {
                if (i >= r || l > i)
                        return;
                if (l + 1 == r)
                {
                        data[index] += val;
                        return;
                }
                cc(index);
                int m = l+r>>1;
                update(l, m, left[index], i, val);
                update(m, r, right[index], i, val);
                data[index] = data[left[index]] + data[right[index]];
        }
        int get(int l, int r, int index, int ss, int ee)
        {
                if (ss >= r || l >= ee)
                        return 0;
                if (ee >= r && l >= ss)
                        return  data[index];
                int m = l+r>>1;
                int lres = 0, rres = 0;
                if (left[index] != -1)
                        lres = get(l, m, left[index], ss, ee);
                if (right[index] != -1)
                        rres = get(m, r, right[index], ss, ee);
                return lres + rres;
        }
        void update(int i, int val) { update(0, n, 0, i, val ); }
        int get(int ss, int ee) { return get(0, n, 0, ss, ee); }
};

void solve1d()
{
        int n, d, m;
        cin >> n >> d >> m;
        SegTree1d st(m);
        vector<int> v(n);
        for (int& i : v)
        {
                cin >> i;
                i--;
                st.update(i, 1);
        }
        int encounters = 0;
        for (int i : v)
                encounters += st.get(i-d, i+d+1) - 1;
        cout << (encounters / 2) << "\n";
}


struct SegTree2d
{
        int ll, rr, uu, dd;
        vector<int> data;
        vector<int> left, right;
        vector<int> root;
        vector<int> down, up;
        SegTree2d (int ll, int rr, int dd, int uu) : ll(ll), rr(rr), uu(uu), dd(dd), root(1, -1), up(1, -1), down(1, -1) {}
        int create_x()
        {
                int res = data.size();
                data.pb(0);
                left.pb(-1);
                right.pb(-1);
                assert(res != -1);
                return res;
        }
        int create_y()
        {
                int res = root.size();
                root.pb(-1);
                down.pb(-1);
                up.pb(-1);
                assert(res != -1);
                return res;
        }
        void update_row(int l, int r, int index, int x, int val)
        {
                if (l + 1 == r)
                {
                        data[index] += val;
                        return;
                }
                int m = l+r>>1;
                if (m > x)
                {
                        if (left[index] == -1)
                        {
                                int tmp = create_x();
                                left[index] = tmp;
                        }
                        assert(left[index] != -1);
                        update_row(l, m, left[index], x, val);
                }
                else
                {
                        if (right[index] == -1)
                        {
                                int tmp = create_x();
                                right[index] = tmp;
                        }
                        assert(right[index] != -1);
                        update_row(m, r, right[index], x, val);
                }
                data[index] = 0;
                if (left[index] != -1)
                        data[index] += data[left[index]];
                if (right[index] != -1)
                        data[index] += data[right[index]];
        }
        void update_grid(int d, int u, int index, int x, int y, int val)
        {
                if (y >= u || d > y)
                        return;
                if (root[index] == -1)
                {
                        int tmp = create_x();
                        root[index] = tmp;
                }
                assert(root[index] != -1);
                update_row(ll, rr, root[index], x, val);
                if (d + 1 == u)
                        return;
                int m = d+u>>1;
                if (m > y)
                {
                        if (down[index] == -1)
                        {
                                int tmp = create_y();
                                down[index] = tmp;;
                        }
                        assert(down[index] != -1);
                        update_grid(d, m, down[index], x, y, val);
                }
                else
                {
                        if (up[index] == -1)
                        {
                                int tmp = create_y();
                                up[index] = tmp;
                        }
                        assert(up[index] != -1);
                        update_grid(m, u, up[index], x, y, val);
                }
        }
        int get_row(int l, int r, int index, int xs, int xe)const
        {
                if (xs >= r || l >= xe || index == -1)
                        return 0;
                if (xe >= r && l >= xs)
                        return data[index];
                int m = l+r>>1;
                int lres = get_row(l, m, left[index], xs, xe);
                int rres = get_row(m, r, right[index], xs, xe);
                return lres + rres;
        }
        int get_grid(int d, int u, int index, int xs, int xe, int ys, int ye)const
        {
                if (ys >= u || d >= ye || index == -1)
                        return 0;
                if (ye >= u && d >= ys)
                        return get_row(ll, rr, root[index], xs, xe);
                int m = d+u>>1;
                int dres = get_grid(d, m, down[index], xs, xe, ys, ye);
                int ures = get_grid(m, u, up[index], xs, xe, ys, ye);
                return dres + ures;
        }
        void update(int x, int y, int val) { update_grid(dd, uu, 0, x, y, val); }
        int get(int xs, int xe, int ys, int ye)const { return get_grid(dd, uu, 0, xs, xe, ys, ye); }
        void clear()
        {
                data.clear();
                root.clear();
                left.clear();
                right.clear();
                up.clear();
                down.clear();
        }
};
const int BOTTOM_LEFT = 0;
const int BOTTOM_RIGHT = 1;
const int TOP_LEFT = 2;
const int TOP_RIGHT = 3;

void solve2d()
{
        int n, d, m;
        cin >> n >> d >> m;
        vector<array<int, 2>> v(n);
        SegTree2d st[] = {SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m), SegTree2d(0, m, -2*m, 2*m) } ;
        for (auto& [x, y] : v)
        {
                cin >> x >> y;
                x--, y--;
        }
        sort(v.begin(), v.end());
        int encounters = 0;
        for (auto [x, y] : v)
        {
                encounters += st[BOTTOM_LEFT].get(0, y+1, -2*m+1, d-x-y+1);
                encounters += st[TOP_LEFT].get(y+1, m, -2*m+1, d-x+y+1);
                st[BOTTOM_LEFT].update(y, -x-y, 1);
                st[TOP_LEFT].update(y, y-x, 1);
        }
        st[BOTTOM_LEFT].clear();
        st[TOP_LEFT].clear();
        for (int i = v.size()-1; i >= 0; i--)
        {
                auto [x, y] = v[i];
                encounters += st[BOTTOM_RIGHT].get(0, y+1, -2*m+1, d+x-y+1);
                encounters += st[TOP_RIGHT].get(y+1, m, -2*m+1, d+x+y+1);
                st[BOTTOM_RIGHT].update(y, x-y, 1);
                st[TOP_RIGHT].update(y, x+y, 1);
        }
        cout << (encounters / 2) << "\n";

}

int32_t main()
{
        int b;
        cin >> b;
        if (b == 1)
                solve1d();
        else if (b == 2)
                solve2d();
        else
                cout << "99\n";
}

Compilation message

pairs.cpp: In member function 'void SegTree1d::update(int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:39:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |                 int m = l+r>>1;
      |                         ~^~
pairs.cpp: In member function 'int64_t SegTree1d::get(int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:50:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                 int m = l+r>>1;
      |                         ~^~
pairs.cpp: In constructor 'SegTree2d::SegTree2d(int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:87:27: warning: 'SegTree2d::up' will be initialized after [-Wreorder]
   87 |         vector<int> down, up;
      |                           ^~
pairs.cpp:87:21: warning:   'std::vector<long int> SegTree2d::down' [-Wreorder]
   87 |         vector<int> down, up;
      |                     ^~~~
pairs.cpp:88:9: warning:   when initialized here [-Wreorder]
   88 |         SegTree2d (int ll, int rr, int dd, int uu) : ll(ll), rr(rr), uu(uu), dd(dd), root(1, -1), up(1, -1), down(1, -1) {}
      |         ^~~~~~~~~
pairs.cpp: In member function 'void SegTree2d::update_row(int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:114:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |                 int m = l+r>>1;
      |                         ~^~
pairs.cpp: In member function 'void SegTree2d::update_grid(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t)':
pairs.cpp:154:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |                 int m = d+u>>1;
      |                         ~^~
pairs.cpp: In member function 'int64_t SegTree2d::get_row(int64_t, int64_t, int64_t, int64_t, int64_t) const':
pairs.cpp:182:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  182 |                 int m = l+r>>1;
      |                         ~^~
pairs.cpp: In member function 'int64_t SegTree2d::get_grid(int64_t, int64_t, int64_t, int64_t, int64_t, int64_t, int64_t) const':
pairs.cpp:193:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  193 |                 int m = d+u>>1;
      |                         ~^~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 42 ms 1336 KB Output is correct
2 Correct 30 ms 1528 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 200 ms 46728 KB Output is correct
2 Correct 130 ms 46620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 232 ms 46528 KB Output is correct
2 Correct 93 ms 9732 KB Output is correct
3 Correct 81 ms 2844 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 31 ms 27700 KB Output is correct
2 Correct 32 ms 27668 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 287 ms 7632 KB Output is correct
2 Correct 317 ms 7620 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1340 ms 180812 KB Output is correct
2 Correct 1360 ms 180892 KB Output is correct
3 Correct 883 ms 83068 KB Output is correct
4 Correct 1206 ms 156496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 2741 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -