Submission #369687

#	Time	Username	Problem	Language	Result	Execution time	Memory
369687		azberjibiou	Examination (JOI19_examination)	C++17	100 / 100	506 ms	16272 KiB

examination

#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
#define fir first
#define sec second
#define ll long long
#define pii pair<int, int>
const int mxN=103000;
typedef struct pro{
    ll a, b, c;
}pro;
typedef struct qry{
    int x, sy, ey, idx, typ;
}qry;
int N, Q;
pro T[mxN];
pii A[mxN];
vector <int> coorx, coory, coorxy;
vector <int> xy;
int ans[mxN];
vector <qry> v;
vector <pii> swp;
int X, Y;
int seg[4*mxN];
bool cmp1(qry p, qry q)
{
    return p.x<q.x;
}
bool cmp2(pii a, pii b)
{
    return a.fir<b.fir;
}
void init(int idx, int s, int e)
{
    seg[idx]=0;
    if(s==e)    return;
    int mid=(s+e)/2;
    init(2*idx, s, mid);
    init(2*idx+1, mid+1, e);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s2>e1 || s1>e2)  return 0;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2);
}
void upd(int idx, int s, int e, int pos)
{
    if(pos<s || pos>e)  return;
    seg[idx]++;
    if(s==e)    return;
    int mid=(s+e)/2;
    upd(2*idx, s, mid, pos);
    upd(2*idx+1, mid+1, e, pos);
}
void make_coor()
{
    for(int i=0;i<N;i++)   coorx.push_back(A[i].fir), coory.push_back(A[i].sec);
    for(int i=0;i<N;i++)   coorxy.push_back(A[i].fir+A[i].sec);
    coorx.push_back(1000000007);
    coory.push_back(1000000007);
    coorx.push_back(-2);
    coory.push_back(-2);
    coorxy.push_back(2000000007);
    coorxy.push_back(-2);
    sort(coorx.begin(), coorx.end());   sort(coory.begin(), coory.end());
    sort(coorxy.begin(), coorxy.end());
    coorx.erase(unique(coorx.begin(), coorx.end()), coorx.end());
    coory.erase(unique(coory.begin(), coory.end()), coory.end());
    coorxy.erase(unique(coorxy.begin(), coorxy.end()), coorxy.end());
    X=coorx.size(), Y=coory.size();
}
int main()
{
    gibon
    cin >> N >> Q;
    for(int i=0;i<N;i++)    cin >> A[i].fir >> A[i].sec;
    for(int i=0;i<Q;i++)    cin >> T[i].a >> T[i].b >> T[i].c;
    make_coor();
    for(int i=0;i<Q;i++)
    {
        int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin();
        int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin();
        //printf("i=%d, nx=%d, ny=%d\n", i, nx, ny);
        v.push_back({X-1, ny, Y-1, i, 1});
        v.push_back({nx-1, ny, Y-1, i, -1});
        if(T[i].a+T[i].b>=T[i].c)   continue;
        v.push_back({nx-1, 0, ny-1, i, -1});
    }
    sort(v.begin(), v.end(), cmp1);
    init(1, 0, Y-1);
    for(int i=0;i<N;i++)
    {
        int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin();
        int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin();
        swp.push_back({nx, ny});
    }
    sort(swp.begin(), swp.end(), cmp2);
    //for(qry ele : v)    printf("ele=%d, %d, %d, %d, %d\n", ele.x, ele.sy, ele.ey, ele.idx, ele.typ);
    int cur=0;
    for(int i=0;i<N;i++)
    {
        while(cur!=v.size() && v[cur].x<swp[i].fir)
        {
            ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
            cur++;
        }
        upd(1, 0, Y-1, swp[i].sec);
    }
    while(cur!=v.size())
    {
        ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
        cur++;
    }
    //for(int i=0;i<Q;i++)    printf("ans[%d]=%d\n", i, ans[i]);
    ///-------------------------
    v.clear();
    for(int i=0;i<Q;i++)
    {
        if(T[i].a+T[i].b>=T[i].c)   continue;
        int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin();
        int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1;
        v.push_back({nxy, ny, Y-1, i, -1});
    }
    sort(v.begin(), v.end(), cmp1);
    swp.clear();
    for(int i=0;i<N;i++)
    {
        int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin();
        int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin();
        swp.push_back({nxy, ny});
    }
    sort(swp.begin(), swp.end(), cmp2);
    init(1, 0, Y-1);
    cur=0;
    for(int i=0;i<N;i++)
    {
        while(cur!=v.size() && v[cur].x<swp[i].fir)
        {
            ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
            cur++;
        }
        upd(1, 0, Y-1, swp[i].sec);
    }
    while(cur!=v.size())
    {
        ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ;
        cur++;
    }
    //for(int i=0;i<Q;i++)    printf("ans[%d]=%d\n", i, ans[i]);
    ///--------------------------
    v.clear();
    for(int i=0;i<Q;i++)
    {
        if(T[i].a+T[i].b>=T[i].c)   continue;
        int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1;
        int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin();
        v.push_back({nxy, nx, X-1, i, -1});
    }
    sort(v.begin(), v.end(), cmp1);
    swp.clear();
    for(int i=0;i<N;i++)
    {
        int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin();
        int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin();
        swp.push_back({nxy, nx});
    }
    sort(swp.begin(), swp.end(), cmp2);
    init(1, 0, X-1);
    cur=0;
    for(int i=0;i<N;i++)
    {
        while(cur!=v.size() && v[cur].x<swp[i].fir)
        {
            ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ;
            cur++;
        }
        upd(1, 0, X-1, swp[i].sec);
    }
    while(cur!=v.size())
    {
        ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ;
        cur++;
    }
    //for(int i=0;i<Q;i++)    printf("ans[%d]=%d\n", i, ans[i]);
    ///-------------------

    for(int i=0;i<N;i++)    xy.push_back(A[i].fir+A[i].sec);
    sort(xy.begin(), xy.end());
    for(int i=0;i<Q;i++)
    {
        if(T[i].a+T[i].b>=T[i].c)   continue;
        ans[i]+=lower_bound(xy.begin(), xy.end(), T[i].c)-xy.begin();
    }
    for(int i=0;i<Q;i++)    cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:111:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~
examination.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~
examination.cpp:174:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:181:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~

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