Submission #683651

#	Time	Username	Problem	Language	Result	Execution time	Memory
683651		billyisme	Pairs (IOI07_pairs)	C++14	60 / 100	4075 ms	2780 KiB

pairs

#define TASK "pair"
#define INPUT TASK".INP" 
#define OUTPUT TASK".OUT"
#include<bits/stdc++.h>
using namespace std; 
bool multitest = false;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long 
#define db double 
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll> 
#define ve vector 
#define str string 
#define fi first 
#define se second  
#define pb push_back 
#define pk pop_back 
#define el '\n'
#define mp make_pair 
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define FORD(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define FORN(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(a) a.begin(),a.end() 
#define btpc(a) __builtin_popcount(a) 
ll sq(ll a){return a*a;}  
ll gcd(ll a, ll b){return b ==0 ? a: gcd(b,a%b);} 
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
void IOS()
{
    fast 
    if(fopen(INPUT,"r"))
    {
        freopen(INPUT ,"r",stdin) ;
        freopen(OUTPUT,"w",stdout) ;
    }
}
const int N = 2e5+5, oo = 2e9, CH = 26, LO = 20; 
const ll inf = 1e17, cs = 330, sm = 1e9+7; 
const db PI = acos(-1) ; 
int xx[] = {0,0,0,-1,1}; 
int yy[] = {0,-1,1,0,0};

int B , n , D ,M ; 
void read()
{
	cin>>B>>n>>D >>M ;
}

void sub1()
{
	vi a(n+1,0) ; 
	FOR(i,1,n)cin>>a[i] ; 
	sort(a.begin()+1,a.begin()+n+1) ;
	int it= 1 ;
	ll res= 0 ; 
	for(int i= 1;i<=n;i++)
	{
		while(a[i]-a[it]>D)++it ;
		res+=abs(i-it);
	}
	cout<<res<<el;
}	
struct DL1
{
	int A , B ;
	bool operator<(const DL1&other)const
	{
		return A<other.A;
	}  
};
int bit1[N] ;
void up1(int idx, int val )
{
	for(int i= idx;i<=150000;i+=i&-i)bit1[i]+=val; 
}
int get1(int idx )
{
	int ans= 0  ;
	for(int i = idx;i;i-=i&-i)ans+=bit1[i] ;
	return ans; 
}
void sub2()
{
	ve<DL1>a(n+1);
	FOR(i,1,n)
	{
		int x , y; 
		cin>>x>>y; 
		a[i] = {x+y,x-y+75000} ; 
	}
	sort(a.begin()+1,a.begin()+n+1);

	int it = 1;
	ll res= 0 ; 
	FOR(i,1,n)
	{
		while((a[i].A-a[it].A)>D)
		{
			up1(a[it].B,-1); 
			++it ;
		}	
		res+=get1(min(150000,a[i].B+D))-get1(max(0,a[i].B-D-1));
		up1(a[i].B,1); 
	} 
	cout<<res ;
}
void sub3()
{
	while(1);
}
signed main()

{
    IOS();
    int test =1;
    if(multitest)cin>>test;
    while(test--)
    {
        read(); 
        if(B==1)sub1() ; 
        if(B==2)sub2() ; 
        if(B==3)sub3() ; 
        // solve();
    }
}

Compilation message (stderr)

pairs.cpp: In function 'void IOS()':
pairs.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(INPUT ,"r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
pairs.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(OUTPUT,"w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10