글 읽기 - 어디서 틀렸을까요? 😥

(追記) (追記ここまで)

어디서 틀렸을까요? 😥

11012번 - Egg

tommy1024 2년 전 0

논리상 문제가 없어 보이는데 계속 틀렸습니다 를 받고 있습니다.

코드의 반례나 문제점이 있을까요? 도와주세요...

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll LN=100005;
ll T,N,M;
ll X[LN],Y[LN];
struct node{
 ll v;
 node *l,*r;
 node(){v=0,l=r=nullptr;}
};
node *root[LN];
void build(node *n,ll l,ll r){
 if(l==r){
 return;
 }
 ll m=(l+r)/2;
 n->l=new node;n->r=new node;
 build(n->l,l,m);build(n->r,m+1,r);
}
void update(ll p,ll val,node *prv,node *n,ll l,ll r){
 if(l==r){
 n->v+=val;
 return;
 }
 ll m=(l+r)/2;
 n->l=prv->l;
 n->r=prv->r;
 if(p<=m){
 node *tmp=n->l;
 n->l=new node;
 n->r=prv->r;
 update(p,val,tmp,n->l,l,m);
 }
 else{
 node *tmp=n->r;
 n->r=new node;
 n->l=prv->l;
 update(p,val,tmp,n->r,m+1,r);
 }
 n->v=n->l->v+n->r->v;
}
ll query(ll ql,ll qr,node *n,ll l,ll r){
 if(qr<l||r<ql)return 0;
 if(ql<=l&&r<=qr)return n->v;
 ll m=(l+r)/2;
 return query(ql,qr,n->l,l,m)+query(ql,qr,n->r,m+1,r);
}
vector<ll> v[LN];
int main()
{
 scanf("%lld",&T);
 while(T--){
 for(ll i=0;i<LN;i++)v[i].clear();
 scanf("%lld%lld",&N,&M);
 for(ll i=1;i<=N;i++){
 scanf("%lld%lld",&X[i],&Y[i]);
 X[i]++;Y[i]++; // 범위를 1~100001로 만듦
 v[X[i]].push_back(Y[i]);
 }
 root[0]=new node;
 build(root[0],1,100001);
 for(ll i=1;i<=100001;i++){
 root[i]=new node;
 root[i]->l=root[i-1]->l;
 root[i]->r=root[i-1]->r;
 root[i]->v=root[i-1]->v;
 for(ll j:v[i]){
 update(j,1,root[i],root[i],1,100001);
 }
 }
 ll ans=0;
 for(ll i=1;i<=M;i++){
 ll l,r,b,t;
 scanf("%lld%lld%lld%lld",&l,&r,&b,&t);
 l++,r++,b++,t++;
 ans+=query(b,t,root[r],1,100001)-query(b,t,root[l-1],1,100001);
 }
 printf("%lld\n",ans);
 }
 return 0;
}

tommy1024 2년 전 2

자답합니다.
반례를 찾았습니다...

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

어디서 틀렸을까요? 😥

tommy1024 2년 전 0

tommy1024 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말