oj.uz

Submission #918225

# Submission time Handle Problem Language Result Execution time Memory
918225 2024-01-29T13:39:07 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((long long)(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((long long)(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++)
    {
        long long d1 = v[i].second - v[i].first;
        long long 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 1938 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 2392 KB Output is correct
2 Correct 1 ms 2392 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 2648 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 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 2648 KB Output is correct
8 Correct 1 ms 2392 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 2392 KB Output is correct
2 Correct 1 ms 2392 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 2648 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 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 2392 KB Output is correct
2 Correct 1 ms 2392 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 2648 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 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 164 ms 27692 KB Output is correct
15 Correct 233 ms 28968 KB Output is correct
16 Correct 234 ms 27700 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 20.0

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