Submission #472026

#	Time	Username	Problem	Language	Result	Execution time	Memory
472026		starplat	Examination (JOI19_examination)	C++14	100 / 100	899 ms	26172 KiB

examination

#include <bits/stdc++.h>
using namespace std;
int n,q,t[200005<<2],ct,ans[200005];
struct edge{
    int a,b,c,op,id;
}e[200005];
vector<int> v;
vector<edge> in,qu;
map<int,int> mp;
int cmp1(edge l,edge r)
{
    if (l.a!=r.a) return l.a>r.a;
    else return l.op<r.op;
}
int cmp2(edge l,edge r)
{
    if (l.b!=r.b) return l.b>r.b;
    else if (l.c!=r.c) return l.c<r.c;
    else return l.id<r.id;
}
void clean(int id,int x,int y)
{
    if (t[id]==0) return;
    t[id]=0;
    if (x!=y){
        int mid=(x+y)/2;
        clean(id*2,x,mid);
        clean(id*2+1,mid+1,y);
    }
}
void update(int id,int x,int y,int pos)
{
    if (x==y) t[id]++;
    else {
        int mid=(x+y)/2;
        if (pos<=mid) update(id*2,x,mid,pos);
        else update(id*2+1,mid+1,y,pos);
        t[id]=t[id*2+1]+t[id*2];
    }
}
int query(int id,int x,int y,int l,int r)
{
    if (l<=x&&y<=r) return t[id];
    if (x>r||y<l) return 0;
    int mid=(x+y)/2;
    return query(id*2,x,mid,l,r)+query(id*2+1,mid+1,y,l,r);
}
void check(int id,int x,int y)
{
	if (!t[id]) return;
	if (x!=y){
		int mid=(x+y)/2;
		check(id*2,x,mid);
		check(id*2+1,mid+1,y);
	}
}
void cdq(int l,int r)
{
    if (l>=r) return;
    int mid=(l+r)/2;
    cdq(l,mid);cdq(mid+1,r);
    in.clear();
    qu.clear();
    for (int i=l;i<=mid;i++) if (!e[i].op) in.push_back(e[i]);
    for (int i=mid+1;i<=r;i++) if (e[i].op) qu.push_back(e[i]);
    sort(in.begin(),in.end(),cmp2);
    sort(qu.begin(),qu.end(),cmp2);
    clean(1,1,ct);
    int pt=0;
    for (edge i:qu){
        while (pt<in.size()&&in[pt].b>=i.b){
            update(1,1,ct,in[pt].c);
            pt++;
        }
        ans[i.id]+=query(1,1,ct,i.c,ct);
    }
    //separate query and insert 
    //sweep insert and query like
    //doing task2126 hedgehog... algorithm 
    //to avoid query comes before insert
    //0 100 3 4
    //35 100 6 0
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for (int i=1;i<=n;i++){
        cin>>e[i].a>>e[i].b;
        e[i].c=e[i].a+e[i].b;
        e[i].op=0;
        v.push_back(e[i].c);
    }
    for (int i=n+1;i<=n+q;i++){
        cin>>e[i].a>>e[i].b>>e[i].c;
        e[i].op=1,e[i].id=i-n;
        v.push_back(e[i].c);
    }
    sort(v.begin(),v.end());
    for (int i:v) if(!mp[i]) mp[i]=++ct;
    for (int i=1;i<=n+q;i++) e[i].c=mp[e[i].c];
    sort(e+1,e+n+q+1,cmp1);
    cdq(1,n+q);
    for (int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'void cdq(int, int)':
examination.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while (pt<in.size()&&in[pt].b>=i.b){
      |                ~~^~~~~~~~~~

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