Submission #374946

#	Time	Username	Problem	Language	Result	Execution time	Memory
374946		BartolM	Examination (JOI19_examination)	C++17	100 / 100	246 ms	16604 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
typedef pair <pii, pii> ppp;

const int INF=0x3f3f3f3f;
const int N=100005;
const int MAX=4*N;

struct Fen{
    int F[MAX];
    Fen() {
        memset(F, 0, sizeof F);
    }
    void update(int x, int val) {
        for (x++; x<MAX; x+=x&-x) F[x]+=val;
    }
    int query(int x) {
        int ret=0;
        for (x++; x>0; x-=x&-x) ret+=F[x];
        return ret;
    }
    void reset() {
        memset(F, 0, sizeof F);
    }
};

int n, q;
pii p[N];
vector <ppp> que1, que2;
vector <int> saz;
int desaz[MAX], sol[N];
Fen xx, yy;

int cmp_zb(pii a, pii b) {
    return desaz[a.X]+desaz[a.Y]>desaz[b.X]+desaz[b.Y];
}

int cmp1(ppp a, ppp b) {
    return a.Y.X>b.Y.X;
}

void sazmi(int &x) {
    int ret=lower_bound(saz.begin(), saz.end(), x)-saz.begin();
    desaz[ret]=x;
    x=ret;
}


void solve() {
    sort(p, p+n, cmp_zb);
    sort(que1.begin(), que1.end(), cmp1);
    int ind=0;
    for (int i=0; i<=n; ++i) {
        int zbr=desaz[p[i].X]+desaz[p[i].Y];
        if (i==n) zbr=-1;
        while (ind<que1.size() && que1[ind].Y.X>zbr) {
            sol[que1[ind].Y.Y]=i-xx.query(que1[ind].X.X-1)-yy.query(que1[ind].X.Y-1);
            ind++;
        }
        xx.update(p[i].X, 1);
        yy.update(p[i].Y, 1);
    }
    sort(p, p+n); reverse(p, p+n);
    sort(que2.begin(), que2.end());
    reverse(que2.begin(), que2.end());
    yy.reset();
    ind=0;
    for (int i=0; i<=n; ++i) {
        int curr= i==n ? -1 : p[i].X;
        while (ind<que2.size() && que2[ind].X.X>curr) {
            sol[que2[ind].Y.Y]=i-yy.query(que2[ind].X.Y-1);
            ind++;
        }
        if (i<n) yy.update(p[i].Y, 1);
    }

    for (int i=0; i<q; ++i) printf("%d\n", sol[i]);
}

void load() {
    scanf("%d %d", &n, &q);
    for (int i=0; i<n; ++i) {
        scanf("%d %d", &p[i].X, &p[i].Y);
        saz.pb(p[i].X); saz.pb(p[i].Y);
    }
    for (int i=0; i<q; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        if (a+b<c) que1.pb({{a, b}, {c, i}});
        else que2.pb({{a, b}, {c, i}});

        saz.pb(a); saz.pb(b);
    }

    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    for (int i=0; i<n; ++i) sazmi(p[i].X), sazmi(p[i].Y);
    for (int i=0; i<que1.size(); ++i) sazmi(que1[i].X.X), sazmi(que1[i].X.Y);
    for (int i=0; i<que2.size(); ++i) sazmi(que2[i].X.X), sazmi(que2[i].X.Y);

}

int main() {
    load();
    solve();
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void solve()':
examination.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while (ind<que1.size() && que1[ind].Y.X>zbr) {
      |                ~~~^~~~~~~~~~~~
examination.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (ind<que2.size() && que2[ind].X.X>curr) {
      |                ~~~^~~~~~~~~~~~
examination.cpp: In function 'void load()':
examination.cpp:110:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0; i<que1.size(); ++i) sazmi(que1[i].X.X), sazmi(que1[i].X.Y);
      |                   ~^~~~~~~~~~~~
examination.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for (int i=0; i<que2.size(); ++i) sazmi(que2[i].X.X), sazmi(que2[i].X.Y);
      |                   ~^~~~~~~~~~~~
examination.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   92 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   94 |         scanf("%d %d", &p[i].X, &p[i].Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57