oj.uz

Submission #918222

# Submission time Handle Problem Language Result Execution time Memory
918222 2024-01-29T13:37:24 Z devkudawla Lightning Rod (NOI18_lightningrod) C++17
66 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order(it return an iterator input is a value), order_of_key(input is index)
typedef tree<long long, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

template <class T>
void Distinct(T &v, bool sorting = true)
{
    if (sorting)
        sort(begin(v), end(v));
    v.resize(unique(begin(v), end(v)) - begin(v));
}
const int BUF_SZ = 1 << 15;

inline namespace Input
{
    char buf[BUF_SZ];
    int pos;
    int len;
    char next_char()
    {
        if (pos == len)
        {
            pos = 0;
            len = (int)fread(buf, 1, BUF_SZ, stdin);
            if (!len)
            {
                return EOF;
            }
        }
        return buf[pos++];
    }

    int read_int()
    {
        int x;
        char ch;
        int sgn = 1;
        while (!isdigit(ch = next_char()))
        {
            if (ch == '-')
            {
                sgn *= -1;
            }
        }
        x = ch - '0';
        while (isdigit(ch = next_char()))
        {
            x = x * 10 + (ch - '0');
        }
        return x * sgn;
    }
} // namespace Input
inline namespace Output
{
    char buf[BUF_SZ];
    int pos;

    void flush_out()
    {
        fwrite(buf, 1, pos, stdout);
        pos = 0;
    }

    void write_char(char c)
    {
        if (pos == BUF_SZ)
        {
            flush_out();
        }
        buf[pos++] = c;
    }

    void write_int(int x)
    {
        static char num_buf[100];
        if (x < 0)
        {
            write_char('-');
            x *= -1;
        }
        int len = 0;
        for (; x >= 10; x /= 10)
        {
            num_buf[len++] = (char)('0' + (x % 10));
        }
        write_char((char)('0' + x));
        while (len)
        {
            write_char(num_buf[--len]);
        }
        write_char('\n');
    }

    // auto-flush output when program exits
    void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output

const int sz = 10000010;
const int sz1 = 10000010;
int Fenwick[sz] = {0};
int Fenwick1[sz1] = {0};

unordered_map<long long int, int> D1, D2;

// 1 BASED INDEXING
// ALWAYS DECLARE FENWICK TREE GLOBALLY
struct fenwicktree
{
    int n;
    vector<int> v;
    fenwicktree(vector<int> A)
    {
        v.resize(A.size() + 1, 0);
        n = A.size();
        for (int i = 0; i < A.size(); i++)
            Add(i + 1, A[i]);
    }
    int Sum(int i)
    {
        int answer = 0;
        for (; i > 0; i -= (i & (-i)))
            answer += Fenwick[i];
        return answer;
    }
    void Add(int i, int x)
    {
        v[i] += x;
        for (; i <= n; i += (i & (-i)))
            Fenwick[i] += x;
    }
    void Replace(int i, int x)
    {
        int y = v[i];
        v[i] = x;
        for (; i <= n; i += (i & (-i)))
            Fenwick[i] += x - y;
    }
    long long RangeSum(int l, int r)
    {
        return Sum(r) - Sum(l - 1);
    }
};

// 1 BASED INDEXING
// ALWAYS DECLARE FENWICK TREE GLOBALLY
struct fenwicktree1
{
    int n;
    vector<int> v;
    fenwicktree1(vector<int> A)
    {
        v.resize(A.size() + 1, 0);
        n = A.size();
        for (int i = 0; i < A.size(); i++)
            Add(i + 1, A[i]);
    }
    int Sum(int i)
    {
        int answer = 0;
        for (; i > 0; i -= (i & (-i)))
            answer += Fenwick1[i];
        return answer;
    }
    void Add(int i, int x)
    {
        v[i] += x;
        for (; i <= n; i += (i & (-i)))
            Fenwick1[i] += x;
    }
    void Replace(int i, int x)
    {
        int y = v[i];
        v[i] = x;
        for (; i <= n; i += (i & (-i)))
            Fenwick1[i] += x - y;
    }
    long long RangeSum(int l, int r)
    {
        return Sum(r) - Sum(l - 1);
    }
};
//----------------------------------------------------
void solve()
{
    int n;
    n = read_int();
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++)
    {
        int a, b;
        a = read_int();
        b = read_int();
        v[i] = {b, a};
    }
    sort(begin(v), end(v));
    reverse(begin(v), end(v));
    int c1, c2;
    {
        vector<long long> a;
        for (int i = 0; i < n; i++)
            a.push_back(v[i].second - v[i].first);
        Distinct(a);
        for (int i = 0; i < a.size(); i++)
            D1[a[i]] = i + 1;
        c1 = a.size();
        a.clear();
        for (int i = 0; i < n; i++)
            a.push_back(v[i].second + v[i].first);
        Distinct(a);
        c2 = a.size();
        for (int i = 0; i < a.size(); i++)
            D2[a[i]] = i + 1;
    }
    fenwicktree a(vector<int>(c1 + 5, 0));
    fenwicktree1 b(vector<int>(c2 + 5, 0));
    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        int d1 = v[i].second - v[i].first;
        int d2 = v[i].second + v[i].first;
        int p1 = a.RangeSum(1, D1[d1]);
        int p2 = b.RangeSum(D2[d2], c2);
        if (p1 + p2 - answer > 0)
            continue;
        answer++;
        a.Add(D1[d1], 1);
        b.Add(D2[d2], 1);
    }
    write_int(answer);
}
//----------------------------------------------------
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    init_output();

    solve();

    return 0;
}
//----------------------------------------------------

Compilation message

lightningrod.cpp: In constructor 'fenwicktree::fenwicktree(std::vector<int>)':
lightningrod.cpp:121:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for (int i = 0; i < A.size(); i++)
      |                         ~~^~~~~~~~~~
lightningrod.cpp: In constructor 'fenwicktree1::fenwicktree1(std::vector<int>)':
lightningrod.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for (int i = 0; i < A.size(); i++)
      |                         ~~^~~~~~~~~~
lightningrod.cpp: In function 'void solve()':
lightningrod.cpp:209:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  209 |         for (int i = 0; i < a.size(); i++)
      |                         ~~^~~~~~~~~~
lightningrod.cpp:217:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |         for (int i = 0; i < a.size(); i++)
      |                         ~~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1953 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2652 KB Output is correct
14 Correct 226 ms 27588 KB Output is correct
15 Correct 195 ms 28964 KB Output is correct
16 Correct 203 ms 27616 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2020 ms 210384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1953 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -