제출 #103524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
103524		tduong0806	Examination (JOI19_examination)	C++14	100 / 100	821 ms	27248 KiB

examination

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define forinc(i,a,b) for(int i=a;i<=b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
#define read2(a,b) read(a),read(b)
#define read3(a,b,c) read(a),read(b),read(c)
const int N=100010;
int n,m,ans[N];
vector<int> t[N],e,sv[N];
struct oo {int x,y,z,id;} a[N],q[N];
bool cmp(oo u,oo v) {return u.x>v.x;}
int v(int x) {return lower_bound(all(e),x)-e.begin()+1;}
int vz(int i,int x) {return lower_bound(all(sv[i]),x)-sv[i].begin()+1;}
void add(int i,int j)
{
    i=v(i);
    for(;i;i-=i&-i) t[i].pb(0),sv[i].pb(j);
}
void update(int i,int j)
{
    i=v(i);
    for(;i;i-=i&-i)
    {
        int _j=vz(i,j);
        for(;_j;_j-=_j&-_j) t[i][_j]++;
    }
}
int get(int i,int j)
{
    int g=0;
    i=v(i);
    for(;i<=n;i+=i&-i)
    {
        int _j=vz(i,j);
        for(;_j<t[i].size();_j+=_j&-_j) g+=t[i][_j];
    }
    return g;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("Examination.inp","r",stdin);
    cin>>n>>m;
    forinc(i,1,n)
    {
        cin>>a[i].x>>a[i].y,a[i].z=a[i].x+a[i].y;
        e.pb(a[i].y);
    }
    sort(all(e));
    forinc(i,1,m)
    {
        cin>>q[i].x>>q[i].y>>q[i].z;
        q[i].id=i;
    }
    forinc(i,1,n)
    {
        t[i].pb(0);
        add(a[i].y,a[i].z);
    }
    forinc(i,1,n) sort(all(sv[i]));
    sort(a+1,a+n+1,cmp);
    sort(q+1,q+m+1,cmp);
    int top=1;
    forinc(i,1,m)
    {
        while(top<=n&&a[top].x>=q[i].x) update(a[top].y,a[top].z),top++;
        ans[q[i].id]=get(q[i].y,q[i].z);
    }
    forinc(i,1,m) cout<<ans[i]<<"\n";
}

컴파일 시 표준 에러 (stderr) 메시지

examination.cpp: In function 'int get(int, int)':
examination.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;_j<t[i].size();_j+=_j&-_j) g+=t[i][_j];
              ~~^~~~~~~~~~~~

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