Submission #143684

#	Time	Username	Problem	Language	Result	Execution time	Memory
143684		osaaateiasavtnl	Examination (JOI19_examination)	C++14	100 / 100	552 ms	50276 KiB

examination

#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({lw(cy, d[i].miny), -1, i});
            mem[0][r].app({0, -1, i});
            mem[0][r].app({lw(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 (stderr)

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: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57