結果
| 問題 | No.2796 Small Matryoshka |
| ユーザー |
 Pramod Kumar Reddy Ponnathota
|
| 提出日時 | 2024-06-28 22:15:57 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,962 bytes |
| コンパイル時間 | 3,119 ms |
| コンパイル使用メモリ | 203,344 KB |
| 実行使用メモリ | 17,144 KB |
| 最終ジャッジ日時 | 2024-06-28 22:16:02 |
| 合計ジャッジ時間 | 4,784 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 3 ms
10,868 KB |
| testcase_01 | AC | 3 ms
10,904 KB |
| testcase_02 | AC | 3 ms
11,012 KB |
| testcase_03 | AC | 3 ms
10,972 KB |
| testcase_04 | AC | 4 ms
11,040 KB |
| testcase_05 | AC | 12 ms
11,640 KB |
| testcase_06 | AC | 66 ms
15,480 KB |
| testcase_07 | AC | 4 ms
11,092 KB |
| testcase_08 | AC | 52 ms
15,608 KB |
| testcase_09 | AC | 69 ms
16,760 KB |
| testcase_10 | AC | 65 ms
15,740 KB |
| testcase_11 | AC | 65 ms
17,144 KB |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
ソースコード
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define mod 1000000007
#define mod2 998244353
#define ll long long
#define bl __int128_t
#define pb push_back
#define all(v) v.begin(),v.end()
#define bs binary_search
#define rall(v) v.rbegin(),v.rend()
#define lb lower_bound
#define ub upper_bound
#define pl pair<ll,ll>
#define f(i,n) for(ll i=0;i<n;i++)
#define inp(a,n) vector<ll> a(n); f(i,n) cin>>a[i]
#define pyes cout<<"YES\n"
#define pno cout<<"NO\n"
#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt")
/*void mat_mul(ll a[101][101],ll b[101][101],ll mv,ll z){
ll mul[mv][mv];
for (ll i=0;i<mv;i++) for(ll j=0;j<mv;j++){
mul[i][j]=0;
for(ll ki=0;ki<mv;ki++) mul[i][j]+=(a[i][ki]*b[ki][j])%z,mul[i][j]%=z;
}
for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) a[i][j]=mul[i][j]%z; return;
}
void mat_exp(ll a[101][101],ll s[],ll l[],ll n,ll mv,ll z){
ll m[101][101];
for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) m[i][j]=((s[i]*s[j])+(s[i]*l[j])+(s[j]*l[i]));
while(n>0){
if(n%2) mat_mul(a,m,mv,z);
n/=2; mat_mul(m,m,mv,z);
for(ll i=0;i<mv;i++) for(ll j=0;j<mv;j++) a[i][j]%=z,m[i][j]%=z;
}return;
}*/
ll power(ll x,ll y,ll z=LLONG_MAX){
ll res=1;
while(y>0){
if(y%2) res=(res*x)%z;
y/=2;
if(y) x=(x*x)%z;
}return res%z;
}
/*ll gcd(ll a,ll b,ll& x,ll& y){
x=1,y=0;
ll x1=0,y1=1,a1=a,b1=b;
while(b1){
ll q=a1/b1;
tie(x,x1)=make_tuple(x1,x-q*x1);
tie(y,y1)=make_tuple(y1,y-q*y1);
tie(a1,b1)=make_tuple(b1,a1-q*b1);
}return a1;
}*/
vector<ll> isP(1e3+5,1);
void setP(){
isP[0]=isP[1]=0;
for(ll i=2;i*i<1e3+5;i++){
if(isP[i]==1) for(ll j=i*i;j<1e3+5;j+=i) isP[j]=0;
}return;
}
vector<ll> pr;
void getP(){ //pr.push_back(2);
for(ll i=3;i<1e5;i+=2) if(isP[i]) pr.push_back(i); }
#define MX 1e6
vector<ll> spf(MX+2,1);
void sieve(){
spf[0]=0;
for(ll i=2;i<3;i++){
if(spf[i]==1){
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
}
}for(ll i=3;i<MX+1;i+=2){
if(spf[i]==1){
for(ll j=i;j<MX+1;j+=i) if(spf[j]==1) spf[j]=i;
}
}
return;
}
/*ll nCr(ll n,ll r){
if(r>n) return 0;
if(n-r<r) r=n-r;
ll p=1,q=1,m;
while(r){
p*=n,q*=r;
m=__gcd(p,q);
p/=m,q/=m;
n--,r--;
}return p;
}*/
/*#define MX 10000
ll fac[MX+1],numInv[MX+1],facNumInv[MX+1];
void compfac(ll z){
facNumInv[0]=facNumInv[1]=numInv[0]=numInv[1]=fac[0]=1;
for(ll i=2;i<=MX;i++) numInv[i]=numInv[z%i]*(z-z/i)%z;
for(ll i=2;i<=MX;i++) facNumInv[i]=(facNumInv[i-1]*numInv[i])%z;
for(ll i=1;i<=MX;i++) fac[i]=(fac[i-1]*i)%z;
return;
}
ll nCrmod(ll n,ll r,ll z){
if(r>n) return 0;
return (((fac[n]*facNumInv[r])%z)*facNumInv[n-r])%z;
}*/
/*
vector<ll> getPF(ll x){
vector<ll> res;
map<ll,ll> mp;
while(x!=1){
if(mp[spf[x]]==0) res.push_back(spf[x]);
mp[spf[x]]++,x/=spf[x];
}return res;
}*/
/*bool isBipc(vector<vector<ll>>& v2,ll src,vector<ll>& color){
color[src] = 1;
queue<ll> q;
q.push(src);
while (!q.empty()) {
ll u = q.front();
q.pop();
for(auto z : v2[u]){
if(color[z]==-1) color[z]=1-color[u],q.push(z);
else if(color[z]==color[u]) return false;
}
}return true;
}
bool isBip(vector<vector<ll>>& v2,vector<ll>& color){
ll n=v2.size(),i;
for(i=1;i<=n;i++) if(color[i]==-1 && !(isBipc(v2,i,color))) return false;
return true;
}*/
/*ll num1,num2;
template<class T, class U>
// T -> node, U->update.
struct Lsegtree{
vector<T>st;
vector<U>lazy;
ll n;
T identity_element; // related to query
U identity_update; // related to update
Lsegtree(ll n, T identity_element, U identity_update)
{
this->n = n;
this->identity_element = identity_element;
this->identity_update = identity_update;
st.assign(4*n,identity_element);
lazy.assign(4*n, identity_update);
}
T combine(T l, T r)
{
// change this function as required.
// related to query
T ans = max(l,r);
return ans;
}
void buildUtil(ll v, ll tl, ll tr, vector<T>&a)
{
if(tl == tr)
{
st[v]=a[tl];
return;
}
ll tm = (tl + tr)/2;
buildUtil(2*v + 1, tl, tm,a);
buildUtil(2*v + 2,tm+1,tr,a);
st[v] = combine(st[2*v + 1], st[2*v + 2]);
}
// change the following 2 functions, and you're more or less done.
T apply(T curr, U upd, ll tl, ll tr)
{
// related to update and query
T ans = upd;
return ans;
}
U combineUpdate(U old_upd, U new_upd, ll tl, ll tr)
{
// related to update
U ans = old_upd;
ans=new_upd;
return ans;
}
void push_down(ll v, ll tl, ll tr)
{
if(lazy[v] == identity_update)return;
st[v] = apply(st[v], lazy[v], tl, tr);
if(2*v + 2 < 4*n)
{
ll tm = (tl + tr)>>1;
lazy[2*v + 1] = combineUpdate(lazy[2*v+1], lazy[v], tl, tm);
lazy[2*v + 2] = combineUpdate(lazy[2*v+2], lazy[v], tm+1,tr);
}
lazy[v] = identity_update;
}
T queryUtil(ll v, ll tl, ll tr, ll l, ll r)
{
push_down(v,tl,tr);
if(l > r)return identity_element;
if(tr < l or tl > r)
{
return identity_element;
}
if(l <= tl and r >= tr)
{
return st[v];
}
ll tm = (tl + tr)>>1;
return combine(queryUtil(2*v+1,tl,tm,l,r), queryUtil(2*v+2,tm+1,tr,l,r));
}
void updateUtil(ll v, ll tl, ll tr, ll l, ll r, U upd)
{
push_down(v,tl,tr);
if(tr < l or tl > r)return;
if(tl >=l and tr <=r)
{
lazy[v] = combineUpdate(lazy[v],upd,tl,tr);
push_down(v,tl,tr);
}
else
{
ll tm = (tl + tr)/2;
updateUtil(2*v+1,tl,tm,l,r,upd);
updateUtil(2*v+2,tm+1,tr,l,r,upd);
st[v] = combine(st[2*v + 1], st[2*v+2]);
}
}
void build(vector<T>a)
{
assert(a.size() == n);
buildUtil(0,0,n-1,a);
}
T query(ll l, ll r)
{
return queryUtil(0,0,n-1,l,r);
}
void update(ll l,ll r, U upd)
{
updateUtil(0,0,n-1,l,r,upd);
}
ll find_ind(ll v,ll tl,ll tr,ll x){
// have to store maximums for this to work
if(st[v]<x) return 0;
if(tl==tr) return tl;
ll tm=(tl+tr)/2;
if(st[v+v+1]>=x) return find_ind(v+v+1,tl,tm,x);
else return find_ind(v+v+2,tm+1,tr,x-st[v+v+1]);
}
};*/
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
ll t=1,i,j,n,m,z=1e9+7,z2=998244353,k,x,y,q;
//sieve(); // for SPF
//setP();
//getP();
//cin>>t;
map<ll,ll> mp,mp2,mp3;
//compfac(z2);
string s,s2;
while(t--){
cin>>n;
vector<pl> v;
f(i,n){
cin>>x>>y;
v.pb({x,y});
}sort(all(v));
ll ans=-1;
vector<bool> vis(n,false);
f(i,n){
if(vis[i]) continue;
int ind=i;
while(ind<n){
pl cur={v[ind].second,0ll};
vis[ind]=1;
ind=lb(all(v),cur)-v.begin();
}ans++;
}cout<<ans<<endl;
}
return 0;
}