Submission #1079831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079831		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	462 ms	49444 KiB

examination

// #pragma GCC optimize("O3","unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5;
struct Node{
    int x,y,s,ty;
};
vector <Node> v;
int n,q,ans[N+5];
void Rs(int l, int r){
    int md=l+r>>1;
    int x=l,y=md+1;
    vector <Node> dq;
    while (x<=md || y<=r){
        if (x>md) dq.push_back(v[y++]);
        else if (y>r) dq.push_back(v[x++]);
        else if (v[x].y<v[y].y) dq.push_back(v[x++]);
        else dq.push_back(v[y++]);
    }
    for (int i=r;i>=l;--i){
        v[i]=dq.back();
        dq.pop_back();
    }
}
bool comp(Node a, Node b){
    if (a.x!=b.x) return a.x<b.x;
    if (a.y!=b.y) return a.y<b.y;
    if (a.s!=b.s) return a.s<b.s;
    return a.ty>b.ty;
}
struct Fenwick_Tree{
    int FT[N+5];
    void clear(){
        for (int i=1;i<=N;++i) FT[i]=0;
    }
    void Update(int idx, int val){
        for (;idx<=N;idx+=idx&(-idx)) FT[idx]+=val;
    }
    int Get(int idx){
        int val=0;
        for (;idx;idx-=idx&(-idx)) val+=FT[idx];
        return val;
    }
    int Sum(int l, int r){
        return Get(r)-Get(l-1);
    }
} fw;
void dnc(int l, int r){
    if (l>=r) return;
    int md=l+r>>1;
    dnc(l,md);
    dnc(md+1,r);
    int pointer=md+1;
    for (int i=md+1;i<=r;++i) 
        if (!v[i].ty) fw.Update(v[i].s,1);
    for (int i=l;i<=md;++i){
        while (pointer<=r && v[pointer].y<v[i].y){
            if (!v[pointer].ty) fw.Update(v[pointer].s,-1);
            ++pointer;
        }
        if (v[i].ty) ans[v[i].ty]+=fw.Sum(v[i].s,N);
    }
    for (int i=pointer;i<=r;++i)
        if (!v[i].ty) fw.Update(v[i].s,-1);
    Rs(l,r);
}
void Solve(){
    cin>>n>>q;
    v.push_back({0,0,0,0});
    for (int i=1;i<=n;++i){
        int x,y;
        cin>>x>>y;
        v.push_back({x,y,x+y,0});
    }
    for (int i=1;i<=q;++i){
        int x,y,z;
        cin>>x>>y>>z;
        v.push_back({x,y,z,i});
    }
    sort(v.begin()+1,v.end(),comp);
    map <int,int> mp,cnt;
    for (int i=1;i<=n+q;++i) mp[v[i].s]=1;
    int idx=0;
    for (pair <int,int> x : mp)
        cnt[x.first]=++idx;
    for (int i=1;i<=n+q;++i) v[i].s=cnt[v[i].s];
    // for (int i=1;i<=n+q;++i) cout<<v[i].x<<' '<<v[i].y<<' '<<v[i].s<<"\n";
    // cout<<"\n";
    dnc(1,n+q);
    for (int i=1;i<=q;++i) cout<<ans[i]<<"\n";
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (fopen("file.inp","r")){
        freopen ("file.inp","r",stdin);
        freopen ("file.out","w",stdout);
    }
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC <<"ms.";
}

Compilation message (stderr)

examination.cpp: In function 'void Rs(long long int, long long int)':
examination.cpp:13:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int md=l+r>>1;
      |            ~^~
examination.cpp: In function 'void dnc(long long int, long long int)':
examination.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int md=l+r>>1;
      |            ~^~
examination.cpp: In function 'int main()':
examination.cpp:98:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen ("file.inp","r",stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:99:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen ("file.out","w",stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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