제출 #121984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
121984		MvC	Examination (JOI19_examination)	C++14	0 / 100	3077 ms	270560 KiB

examination

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=6e5+50;
const int mod=1e9+7;
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int,int>,null_type,less<pair<int,int> >,rb_tree_tag,tree_order_statistics_node_update> order_set;
inline int readChar();
template <class T = int> inline T readInt(); 
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
     
/** Read */
     
static const int buf_size = 4096;
     
inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len) {
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    }
    if (pos == len) {
        return -1;
    }
    return buf[pos++];
}
     
inline int readChar() {
    int c = getChar();
    while (c <= 32) {
        c = getChar();
    }
    return c;
}
     
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
     
/** Write */
     
static int write_pos = 0;
static char write_buf[buf_size];
     
inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
     
template <class T> 
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;
     
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
     
inline void writeWord( const char *s ) {     while (*s)
writeChar(*s++); }
     
struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher; 
int n,q,i,j,k,a[nmax],b[nmax],c[nmax],x[nmax],y[nmax],rs[nmax],nr,sm[nmax],s;
order_set st[4*nmax];
vector<int>qr[nmax];
vector<pair<int,pair<int,int> > >qrr[nmax],vc;
pair<int,pair<int,int> >p;
void upd(int x,int l,int r,int p,int v)
{
	st[x].in(mkp(v,nr));
	if(l==r)return;
	int mid=(l+r)/2;
	if(p<=mid)upd(2*x,l,mid,p,v);
	else upd(2*x+1,mid+1,r,p,v);
}
int qry(int x,int l,int r,int tl,int tr,int v)
{
	if(l>tr || r<tl)return 0;
	if(l>=tl && r<=tr)
	{
		v--;
		if(st[x].upper_bound(mkp(v,1e6))==st[x].end())return 0;
		pair<int,int> y=*st[x].upper_bound(mkp(v,1e6));
		int z=(int)st[x].size()-st[x].order_of_key(y);
		return z;
	}
	int mid=(l+r)/2;
	return qry(2*x,l,mid,tl,tr,v)+qry(2*x+1,mid+1,r,tl,tr,v);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		x[i]=readInt();
		y[i]=readInt();
		vc.pb(mkp(x[i],mkp(0,i)));
		vc.pb(mkp(y[i],mkp(1,i)));
		vc.pb(mkp(x[i]+y[i],mkp(2,i)));
	}
	for(i=1;i<=q;i++)
	{
		a[i]=readInt();
		b[i]=readInt();
		c[i]=readInt();
		vc.pb(mkp(a[i],mkp(3,i)));
		vc.pb(mkp(b[i],mkp(4,i)));
		vc.pb(mkp(c[i],mkp(5,i)));
	}
	sort(vc.begin(),vc.end());
	for(i=0;i<vc.size();)
	{
		k++;
		for(j=i;j<vc.size();j++)
		{
			if(vc[j].fr!=vc[i].fr)break;
			if(vc[j].sc.fr==2)sm[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==1)y[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==0)x[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==3)a[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==4)b[vc[j].sc.sc]=k;
			else if(vc[j].sc.fr==5)c[vc[j].sc.sc]=k;
		}
		i=j;
	}
	for(i=1;i<=n;i++)
	{
		qr[sm[i]].pb(i);
	}
	for(i=1;i<=q;i++)
	{
		qrr[c[i]].pb(mkp(i,mkp(a[i],b[i])));
	}
	for(i=k;i>=1;i--)
	{
		for(j=0;j<qr[i].size();j++)
		{
			s=qr[i][j];
			nr++;
			upd(1,1,k,x[s],y[s]);
		}
		for(j=0;j<qrr[i].size();j++)
		{
			p=qrr[i][j];
			rs[p.fr]=qry(1,1,k,p.sc.fr,k,p.sc.sc);
		}
	}
	for(i=1;i<=q;i++)cout<<rs[i]<<'\n';
    return 0;
}

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

examination.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
examination.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
examination.cpp: In function 'int main()':
examination.cpp:154:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();)
          ~^~~~~~~~~~
examination.cpp:157:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=i;j<vc.size();j++)
           ~^~~~~~~~~~
examination.cpp:179:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qr[i].size();j++)
           ~^~~~~~~~~~~~~
examination.cpp:185:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<qrr[i].size();j++)
           ~^~~~~~~~~~~~~~

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