oj.uz

Submission #143662

# Submission time Handle Problem Language Result Execution time Memory
143662 2019-08-14T20:26:17 Z osaaateiasavtnl Examination (JOI19_examination) C++14
20 / 100
 413 ms 38100 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
struct Point { int x, y; };
struct Quer { int minx, miny, minsum; };
const int N = 1e5 + 7;
int n, q;
Point a[N]; Quer d[N];
struct Q { int p, f, i; }; vector <Q> mem[2][N];
int ans[N];
void compr(vector <int> &a) { sort(all(a)); a.resize(unique(all(a)) - a.begin()); }
int lw(vector <int> &a, int x) { return lower_bound(all(a), x) - a.begin(); }
int up(vector <int> &a, int x) { return upper_bound(all(a), x) - a.begin(); }
vector <int> cx, cy, csum;
int f[N];
void clear() { for (int i = 0; i < N; ++i) f[i] = 0; }
bool upd(int i, int x, bool rev) { if (rev) i = N - i - 1; for (; i < N; i |= i + 1) f[i] += x; }
int get(int i, bool rev) { if (rev) i = N - i - 1; int ans = 0; for (; i >= 0; i &= i + 1, --i) ans += f[i]; return ans; }
vector <int> add[2][N];
void sc(vector <int> add[N], vector <Q> mem[N], bool rev) {
    clear();
    for (int i = N - 1; i >= 0; --i) {
        for (auto e : add[i]) upd(e, 1, rev);
        for (auto e : mem[i]) ans[e.i] += e.f * get(e.p, rev);
    }
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> q;
    for (int i = 0; i < n; ++i) { cin >> a[i].x >> a[i].y; cx.app(a[i].x); cy.app(a[i].y); csum.app(a[i].x + a[i].y); }
    compr(cx); compr(cy); compr(csum);
    for (int i = 0; i < n; ++i) {
        add[0][lw(cx, a[i].x)].app(lw(cy, a[i].y));
        add[1][lw(cx, a[i].x)].app(lw(csum, a[i].x + a[i].y));
    }
    for (int i = 0; i < q; ++i) {
        cin >> d[i].minx >> d[i].miny >> d[i].minsum; --d[i].minsum;
        int t = lw(cx, d[i].minx);
        mem[0][t].app({lw(cy, d[i].miny), 1, i});
        if (d[i].minsum >= d[i].minx + d[i].miny) {
            int r = up(cx, d[i].minsum - d[i].miny);
            //()()()

            mem[0][t].app({0, 1, i}); 
            mem[0][t].app({up(cy, d[i].miny), -1, i});
            mem[0][r].app({0, -1, i});
            mem[0][r].app({up(cy, d[i].miny), 1, i});
            mem[1][r].app({up(csum, d[i].minsum) - 1, 1, i});
            mem[1][t].app({up(csum, d[i].minsum) - 1, -1, i});

            //)()()(
        }
    }
    sc(add[0], mem[0], 1); sc(add[1], mem[1], 0);
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}

Compilation message

examination.cpp: In function 'bool upd(long long int, long long int, bool)':
examination.cpp:21:97: warning: no return statement in function returning non-void [-Wreturn-type]
 bool upd(int i, int x, bool rev) { if (rev) i = N - i - 1; for (; i < N; i |= i + 1) f[i] += x; }
                                                                                                 ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10488 KB Output is correct
2 Correct 13 ms 10488 KB Output is correct
3 Incorrect 11 ms 10616 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 28156 KB Output is correct
2 Correct 310 ms 28216 KB Output is correct
3 Correct 324 ms 28240 KB Output is correct
4 Correct 228 ms 27448 KB Output is correct
5 Correct 165 ms 26068 KB Output is correct
6 Correct 97 ms 25556 KB Output is correct
7 Correct 260 ms 28300 KB Output is correct
8 Correct 279 ms 28120 KB Output is correct
9 Correct 254 ms 28372 KB Output is correct
10 Correct 154 ms 24816 KB Output is correct
11 Correct 233 ms 27256 KB Output is correct
12 Correct 79 ms 23540 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 28156 KB Output is correct
2 Correct 310 ms 28216 KB Output is correct
3 Correct 324 ms 28240 KB Output is correct
4 Correct 228 ms 27448 KB Output is correct
5 Correct 165 ms 26068 KB Output is correct
6 Correct 97 ms 25556 KB Output is correct
7 Correct 260 ms 28300 KB Output is correct
8 Correct 279 ms 28120 KB Output is correct
9 Correct 254 ms 28372 KB Output is correct
10 Correct 154 ms 24816 KB Output is correct
11 Correct 233 ms 27256 KB Output is correct
12 Correct 79 ms 23540 KB Output is correct
13 Incorrect 413 ms 38100 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10488 KB Output is correct
2 Correct 13 ms 10488 KB Output is correct
3 Incorrect 11 ms 10616 KB Output isn't correct
4 Halted 0 ms 0 KB -