이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int N;
int t1[1000000], t2[1000000];
int fid[2000001];
void init()
{
for(int i=0;i<2*N;i++)
fid[i] = i;
}
int find(int i)
{
if(fid[i]==i) return i;
return fid[i] = find(fid[i]);
}
void join(int i,int j)
{
i = find(i), j = find(j);
fid[i] = j;
}
void sameEdge(int i,int j)
{
//cout << "same " << i << ' ' << j << '\n';
join(2*i,2*j);
join(2*i+1,2*j+1);
}
void difEdge(int i,int j)
{
join(2*i+1,2*j);
join(2*i,2*j+1);
}
#define SEG (1<<21)
int up[2*SEG],l[2*SEG],r[2*SEG],seg[2*SEG],cont[2*SEG];
int rIndex[2000000];
void segInit()
{
for(int i=SEG;i<2*SEG;i++)
l[i] = r[i] = i-SEG, up[i] = -1;
for(int i=SEG-1;i>0;i--)
l[i] = l[2*i], r[i] = r[2*i+1], up[i] = -1;
}
void push(int i)
{
if(up[i]>-1)
{
if(i<SEG)
{
if(up[2*i]>-1 && seg[2*i]>0) sameEdge(up[i],up[2*i]);
if(up[2*i+1]>-1 && seg[2*i+1]>0) sameEdge(up[i],up[2*i+1]);
up[2*i] = up[2*i+1] = up[i];
}
else if(rIndex[i-SEG]>-1 && cont[i])
{
difEdge(rIndex[i-SEG],up[i]);
}
up[i] = -1;
}
}
int low,high;
void update(int i,int p)
{
if((l[i]>high)||(r[i]<low)) return;
if((l[i]>=low)&&(r[i]<=high))
{
push(i);
//cout << "Set " << p << " at " << l[i] << " to " << r[i] << '\n';
up[i] = p;
return;
}
push(i);
update(2*i,p);
update(2*i+1,p);
}
int getSum(int i)
{
if((l[i]>high)||(r[i]<low)) return 0;
if((l[i]>=low)&&(r[i]<=high)) return seg[i];
return getSum(2*i) + getSum(2*i+1);
}
void add(int i)
{
int j = 1;
while(j < SEG)
{
push(j);
seg[j]++;
if(i <= r[2*j]) j = 2*j;
else j = 2*j+1;
}
push(j);
cont[i+SEG] = 1;
seg[i+SEG] = 1;
}
int compAns[2000000];
int main()
{
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d %d",&t1[i],&t2[i]);
rIndex[t1[i]] = -1;
rIndex[t2[i]] = i;
}
init();
segInit();
for(int i=0;i<N;i++)
{
low = t1[i];
high = t2[i];
update(1,i);
add(t2[i]);
}
for(int i=1;i<2*SEG;i++)
push(i);
for(int i=0;i<N;i++)
{
if(find(2*i) == find(2*i+1))
{
printf("NIE\n");
return 0;
}
compAns[find(2*i)] = 1;
compAns[find(2*i+1)] = 2;
}
printf("TAK\n");
for(int i=0;i<N;i++)
printf("%d ",compAns[find(2*i)]);
printf("\n");
}
컴파일 시 표준 에러 (stderr) 메시지
port_facility.cpp: In function 'int main()':
port_facility.cpp:115:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
port_facility.cpp:118:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&t1[i],&t2[i]);
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |