oj.uz

Submission #140847

# Submission time Handle Problem Language Result Execution time Memory
140847 2019-08-05T15:57:51 Z karma Examination (JOI19_examination) C++11
100 / 100
 1569 ms 122444 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 pair<int, int> pii;
const int N = int(1e5) + 7;

tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> irene[N];
int Time = 0;

void Update(int x, int y)
{
     for(; x < N; x += (x & -x), ++Time) irene[x].insert(mp(y, Time));
}

int Query(int x, int y)
{
    int res = 0;
    for(; x > 0; x -= (x & -x)) res += irene[x].size() - irene[x].order_of_key(mp(y, -1));
    return res;
}

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

void Enter()
{
     Cin(n, Q); q.resize(Q); a.resize(n); res.resize(Q);
     for(pii& p: a) Cin(p.x, p.y), v.pb(p.y);
     sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
     sort(a.begin(), a.end(), [](const pii& a, const pii& b){return a.x > b.x;});
}

void Solve()
{
     for(int i = 0; i < Q; ++i) Cin(q[i].a, q[i].b, q[i].c), q[i].id = i;
     sort(q.begin(), q.end());
     int j = 0, p;
     for(TQuery que: q) {
         while(a[j].x >= que.a && j < n) {
            p = lower_bound(v.begin(), v.end(), a[j].y) - v.begin() + 1;
            Update(p, a[j].x + a[j].y);
            ++j;
         }
         p = lower_bound(v.begin(), v.end(), que.b) - v.begin();
         res[que.id] = Query(N - 1, que.c) - Query(p, que.c);
     }
     for(int i = 0; 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:98: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:99: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 14 ms 9720 KB Output is correct
2 Correct 14 ms 9720 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct
4 Correct 14 ms 9720 KB Output is correct
5 Correct 14 ms 9720 KB Output is correct
6 Correct 14 ms 9720 KB Output is correct
7 Correct 32 ms 12152 KB Output is correct
8 Correct 31 ms 12152 KB Output is correct
9 Correct 31 ms 12156 KB Output is correct
10 Correct 34 ms 12892 KB Output is correct
11 Correct 29 ms 12124 KB Output is correct
12 Correct 32 ms 12792 KB Output is correct
13 Correct 35 ms 12124 KB Output is correct
14 Correct 30 ms 12152 KB Output is correct
15 Correct 29 ms 12152 KB Output is correct
16 Correct 28 ms 12024 KB Output is correct
17 Correct 37 ms 13176 KB Output is correct
18 Correct 39 ms 13048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1179 ms 72944 KB Output is correct
2 Correct 1184 ms 73040 KB Output is correct
3 Correct 1159 ms 73080 KB Output is correct
4 Correct 976 ms 112116 KB Output is correct
5 Correct 886 ms 72336 KB Output is correct
6 Correct 962 ms 111536 KB Output is correct
7 Correct 1236 ms 72816 KB Output is correct
8 Correct 1073 ms 72968 KB Output is correct
9 Correct 1044 ms 72824 KB Output is correct
10 Correct 787 ms 71980 KB Output is correct
11 Correct 1002 ms 121676 KB Output is correct
12 Correct 1464 ms 120652 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1179 ms 72944 KB Output is correct
2 Correct 1184 ms 73040 KB Output is correct
3 Correct 1159 ms 73080 KB Output is correct
4 Correct 976 ms 112116 KB Output is correct
5 Correct 886 ms 72336 KB Output is correct
6 Correct 962 ms 111536 KB Output is correct
7 Correct 1236 ms 72816 KB Output is correct
8 Correct 1073 ms 72968 KB Output is correct
9 Correct 1044 ms 72824 KB Output is correct
10 Correct 787 ms 71980 KB Output is correct
11 Correct 1002 ms 121676 KB Output is correct
12 Correct 1464 ms 120652 KB Output is correct
13 Correct 1451 ms 73452 KB Output is correct
14 Correct 1307 ms 73456 KB Output is correct
15 Correct 1316 ms 73068 KB Output is correct
16 Correct 1094 ms 112476 KB Output is correct
17 Correct 1141 ms 72596 KB Output is correct
18 Correct 973 ms 111344 KB Output is correct
19 Correct 1375 ms 73660 KB Output is correct
20 Correct 1392 ms 73456 KB Output is correct
21 Correct 1430 ms 73376 KB Output is correct
22 Correct 807 ms 71920 KB Output is correct
23 Correct 980 ms 121584 KB Output is correct
24 Correct 1475 ms 120628 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 9720 KB Output is correct
2 Correct 14 ms 9720 KB Output is correct
3 Correct 14 ms 9848 KB Output is correct
4 Correct 14 ms 9720 KB Output is correct
5 Correct 14 ms 9720 KB Output is correct
6 Correct 14 ms 9720 KB Output is correct
7 Correct 32 ms 12152 KB Output is correct
8 Correct 31 ms 12152 KB Output is correct
9 Correct 31 ms 12156 KB Output is correct
10 Correct 34 ms 12892 KB Output is correct
11 Correct 29 ms 12124 KB Output is correct
12 Correct 32 ms 12792 KB Output is correct
13 Correct 35 ms 12124 KB Output is correct
14 Correct 30 ms 12152 KB Output is correct
15 Correct 29 ms 12152 KB Output is correct
16 Correct 28 ms 12024 KB Output is correct
17 Correct 37 ms 13176 KB Output is correct
18 Correct 39 ms 13048 KB Output is correct
19 Correct 1179 ms 72944 KB Output is correct
20 Correct 1184 ms 73040 KB Output is correct
21 Correct 1159 ms 73080 KB Output is correct
22 Correct 976 ms 112116 KB Output is correct
23 Correct 886 ms 72336 KB Output is correct
24 Correct 962 ms 111536 KB Output is correct
25 Correct 1236 ms 72816 KB Output is correct
26 Correct 1073 ms 72968 KB Output is correct
27 Correct 1044 ms 72824 KB Output is correct
28 Correct 787 ms 71980 KB Output is correct
29 Correct 1002 ms 121676 KB Output is correct
30 Correct 1464 ms 120652 KB Output is correct
31 Correct 1451 ms 73452 KB Output is correct
32 Correct 1307 ms 73456 KB Output is correct
33 Correct 1316 ms 73068 KB Output is correct
34 Correct 1094 ms 112476 KB Output is correct
35 Correct 1141 ms 72596 KB Output is correct
36 Correct 973 ms 111344 KB Output is correct
37 Correct 1375 ms 73660 KB Output is correct
38 Correct 1392 ms 73456 KB Output is correct
39 Correct 1430 ms 73376 KB Output is correct
40 Correct 807 ms 71920 KB Output is correct
41 Correct 980 ms 121584 KB Output is correct
42 Correct 1475 ms 120628 KB Output is correct
43 Correct 1409 ms 68508 KB Output is correct
44 Correct 1411 ms 73272 KB Output is correct
45 Correct 1271 ms 73336 KB Output is correct
46 Correct 1119 ms 113864 KB Output is correct
47 Correct 1029 ms 71792 KB Output is correct
48 Correct 1014 ms 111216 KB Output is correct
49 Correct 1477 ms 73264 KB Output is correct
50 Correct 1270 ms 73328 KB Output is correct
51 Correct 1279 ms 73256 KB Output is correct
52 Correct 906 ms 71532 KB Output is correct
53 Correct 1569 ms 122444 KB Output is correct