oj.uz

Submission #140842

# Submission time Handle Problem Language Result Execution time Memory
140842 2019-08-05T15:28:07 Z karma Examination (JOI19_examination) C++11
43 / 100
 2964 ms 1048576 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define FileName      "test"
#define ll            long long
#define ld            long double
#define ull           unsigned long long
#define Debug(x)      cerr << #x << "is " << x << '\n';
#define pb            emplace_back
#define mp            make_pair
#define x             first
#define y             second
//#define LuckyAurora
//#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

using namespace std;
using namespace __gnu_pbds;

template<typename T> inline void Cin(T &x)
{
    char c;
    T sign = 1;
    x = 0;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        if (c == '-') sign = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sign;
}
template <typename T> inline void Out(T x) {if(x > 9) Out(x / 10); putchar(x % 10 + '0');}
template <typename T> inline void Cout(T x, char c) {if(x < 0) putchar('-'); x = abs(x); Out(x); putchar(c);}
template <typename T, typename... Args> inline void Cin(T& a, Args&... args) {Cin(a);Cin(args...);}
template <typename T, typename... Args> inline void Cout(T a, char c, Args... args) {Cout(a, c);Cout(args...);}
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

typedef pair<int, int> pii;
const int N = int(1e5) + 7;

struct TSegment
{
    bool Get(int x, int i) {return (x >> i) & 1;}
    struct TTrie {TTrie* chil[2]; int cur;} *t[N << 2];
    typedef TTrie* PTrie;
    PTrie Node()
    {
          PTrie ptr = new TTrie();
          ptr -> chil[0] = ptr -> chil[1] = NULL, ptr -> cur = 0;
          return ptr;
    }
    void Update(int x, PTrie ptr)
    {
         bool bit; ++ptr -> cur;
         for(int i = 31; i >= 0; --i) {
            bit = Get(x, i);
            if(ptr -> chil[bit] == NULL) ptr -> chil[bit] = Node();
            ptr = ptr -> chil[bit];
            ++ptr -> cur;
         }
    }
    int Count(int x, PTrie ptr)
    {
        int res = ptr -> cur; bool bit;
        for(int i = 31; i >= 0; --i) {
            bit = Get(x, i);
            if(bit && ptr -> chil[0]) res -= ptr -> chil[0] -> cur;
            if(ptr -> chil[bit] == NULL) return res;
            ptr = ptr -> chil[bit];
        }
        return res;
    }
    int l[N << 2], h[N << 2];
    void Build(int x, int low, int high)
    {
        l[x] = low, h[x] = high; t[x] = Node();
        if(l[x] == h[x]) {return;}
        int mid = (low + high) >> 1;
        Build(x << 1, low, mid);
        Build(x << 1 | 1, mid + 1, high);
    }
    void Update(int x, int pos, int val)
    {
        if(l[x] > pos || h[x] < pos) return;
        if(l[x] <= pos && pos <= h[x]) Update(val, t[x]);
        if(l[x] == h[x]) return;
        Update(x << 1, pos, val);
        Update(x << 1 | 1, pos, val);
    }
    int Query(int x, int low, int high, int val)
    {
        if(l[x] > high || h[x] < low) return 0;
        if(l[x] >= low && h[x] <= high) return Count(val, t[x]);
        return Query(x << 1, low, high, val) + Query(x << 1 | 1, low, high, val);
    }
} irene;

int n, Q, res[N];
pii a[N];
vector<int> v;
struct TQuery
{
    int a, b, c, id;
    bool operator <(const TQuery& other)const& {
        return a > other.a;
    }
} q[N];

void Enter()
{
     cin >> n >> Q;
     for(int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y; v.pb(a[i].y);
     }
     sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
     sort(a + 1, a + n + 1, [](const pii& a, const pii& b){
             return a.x > b.x;
          });
}

void Solve()
{
     for(int i = 1; i <= Q; ++i) {
        cin >> q[i].a >> q[i].b >> q[i].c;
        q[i].id = i;
     }
     sort(q + 1, q + Q + 1);
     int j = 1, p; irene.Build(1, 1, int(v.size()));
     for(int i = 1; i <= Q; ++i) {
         while(a[j].x >= q[i].a && j <= n) {
            p = lower_bound(v.begin(), v.end(), a[j].y) - v.begin() + 1;
            irene.Update(1, p, a[j].x + a[j].y);
            ++j;
         }
         p = lower_bound(v.begin(), v.end(), q[i].b) - v.begin() + 1;
         res[q[i].id] = irene.Query(1, p, int(v.size()), q[i].c);
     }
     for(int i = 1; i <= Q; ++i) cout << res[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if(fopen(FileName".inp", "r")) {
        freopen(FileName".inp", "r", stdin);
        freopen(FileName".out", "w", stdout);
    }

    /*int nTest; cin >> nTest;
    while(nTest --)*/ Enter(), Solve();

    return 0;
}

Compilation message

examination.cpp:15:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
examination.cpp: In function 'int main()':
examination.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:148:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(FileName".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 67 ms 31324 KB Output is correct
8 Correct 67 ms 31352 KB Output is correct
9 Correct 67 ms 31352 KB Output is correct
10 Correct 22 ms 9592 KB Output is correct
11 Correct 64 ms 26296 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 65 ms 31352 KB Output is correct
14 Correct 65 ms 31396 KB Output is correct
15 Correct 65 ms 31352 KB Output is correct
16 Correct 58 ms 26360 KB Output is correct
17 Correct 8 ms 2424 KB Output is correct
18 Correct 4 ms 504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2438 ms 561056 KB Output is correct
2 Correct 2473 ms 560716 KB Output is correct
3 Correct 2449 ms 561012 KB Output is correct
4 Correct 215 ms 48884 KB Output is correct
5 Correct 1545 ms 223092 KB Output is correct
6 Correct 123 ms 5236 KB Output is correct
7 Correct 2526 ms 561048 KB Output is correct
8 Correct 2437 ms 560860 KB Output is correct
9 Correct 2408 ms 560636 KB Output is correct
10 Correct 1413 ms 211440 KB Output is correct
11 Correct 94 ms 10612 KB Output is correct
12 Correct 61 ms 4852 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2438 ms 561056 KB Output is correct
2 Correct 2473 ms 560716 KB Output is correct
3 Correct 2449 ms 561012 KB Output is correct
4 Correct 215 ms 48884 KB Output is correct
5 Correct 1545 ms 223092 KB Output is correct
6 Correct 123 ms 5236 KB Output is correct
7 Correct 2526 ms 561048 KB Output is correct
8 Correct 2437 ms 560860 KB Output is correct
9 Correct 2408 ms 560636 KB Output is correct
10 Correct 1413 ms 211440 KB Output is correct
11 Correct 94 ms 10612 KB Output is correct
12 Correct 61 ms 4852 KB Output is correct
13 Correct 2661 ms 561328 KB Output is correct
14 Correct 2633 ms 561248 KB Output is correct
15 Correct 2474 ms 561140 KB Output is correct
16 Correct 277 ms 49140 KB Output is correct
17 Correct 1778 ms 223836 KB Output is correct
18 Correct 125 ms 5364 KB Output is correct
19 Correct 2689 ms 561432 KB Output is correct
20 Correct 2670 ms 561576 KB Output is correct
21 Correct 2720 ms 561812 KB Output is correct
22 Correct 1409 ms 211960 KB Output is correct
23 Correct 93 ms 10480 KB Output is correct
24 Correct 61 ms 4784 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 67 ms 31324 KB Output is correct
8 Correct 67 ms 31352 KB Output is correct
9 Correct 67 ms 31352 KB Output is correct
10 Correct 22 ms 9592 KB Output is correct
11 Correct 64 ms 26296 KB Output is correct
12 Correct 6 ms 632 KB Output is correct
13 Correct 65 ms 31352 KB Output is correct
14 Correct 65 ms 31396 KB Output is correct
15 Correct 65 ms 31352 KB Output is correct
16 Correct 58 ms 26360 KB Output is correct
17 Correct 8 ms 2424 KB Output is correct
18 Correct 4 ms 504 KB Output is correct
19 Correct 2438 ms 561056 KB Output is correct
20 Correct 2473 ms 560716 KB Output is correct
21 Correct 2449 ms 561012 KB Output is correct
22 Correct 215 ms 48884 KB Output is correct
23 Correct 1545 ms 223092 KB Output is correct
24 Correct 123 ms 5236 KB Output is correct
25 Correct 2526 ms 561048 KB Output is correct
26 Correct 2437 ms 560860 KB Output is correct
27 Correct 2408 ms 560636 KB Output is correct
28 Correct 1413 ms 211440 KB Output is correct
29 Correct 94 ms 10612 KB Output is correct
30 Correct 61 ms 4852 KB Output is correct
31 Correct 2661 ms 561328 KB Output is correct
32 Correct 2633 ms 561248 KB Output is correct
33 Correct 2474 ms 561140 KB Output is correct
34 Correct 277 ms 49140 KB Output is correct
35 Correct 1778 ms 223836 KB Output is correct
36 Correct 125 ms 5364 KB Output is correct
37 Correct 2689 ms 561432 KB Output is correct
38 Correct 2670 ms 561576 KB Output is correct
39 Correct 2720 ms 561812 KB Output is correct
40 Correct 1409 ms 211960 KB Output is correct
41 Correct 93 ms 10480 KB Output is correct
42 Correct 61 ms 4784 KB Output is correct
43 Runtime error 2964 ms 1048576 KB Execution killed with signal 9 (could be triggered by violating memory limits)
44 Halted 0 ms 0 KB -