Problem:

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k.
Rng can perform the following move arbitrarily many times:

move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

1 \leq N \leq 200,000

(x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).

(y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

Sample Output 2

3
3
1
1
2
3
2



Sample input:
4
1 4
2 3
3 1
4 2


Sample output:
1
1
2
2

Submission status: Wrong Answer

Solution code:
# TODO: 更新ルールの異なる複数のセグ木を作ったときに正しく動くか検証

# 注: PyPy で普通に書いた方が速い


code_segtree = r"""
#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include "structmember.h"

// >>> AtCoder >>>

#ifndef ATCODER_SEGTREE_HPP
#define ATCODER_SEGTREE_HPP 1

#include <algorithm>
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

namespace atcoder {

namespace internal {

// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}

// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP
#include <cassert>
#include <vector>

namespace atcoder {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

#endif  // ATCODER_SEGTREE_HPP

// <<< AtCoder <<<

using namespace std;
using namespace atcoder;
#define PARSE_ARGS(types, ...) if(!PyArg_ParseTuple(args, types, __VA_ARGS__)) return NULL

struct AutoDecrefPtr{
    PyObject* p;
    AutoDecrefPtr(PyObject* _p) : p(_p) {};
    AutoDecrefPtr(const AutoDecrefPtr& rhs) : p(rhs.p) { Py_INCREF(p); };
    ~AutoDecrefPtr(){ Py_DECREF(p); }
    AutoDecrefPtr &operator=(const AutoDecrefPtr& rhs){
        Py_DECREF(p);
        p = rhs.p;
        Py_INCREF(p);
        return *this;
    }
};

static PyObject* segtree_op_py;
static AutoDecrefPtr segtree_op(AutoDecrefPtr a, AutoDecrefPtr b){
    auto tmp = PyObject_CallFunctionObjArgs(segtree_op_py, a.p, b.p, NULL);
    return AutoDecrefPtr(tmp);
}
static PyObject* segtree_e_py;
static AutoDecrefPtr segtree_e(){
    Py_INCREF(segtree_e_py);
    return AutoDecrefPtr(segtree_e_py);
}
static PyObject* segtree_f_py;
static bool segtree_f(AutoDecrefPtr x){
    PyObject* pyfunc_res = PyObject_CallFunctionObjArgs(segtree_f_py, x.p, NULL);
    int res = PyObject_IsTrue(pyfunc_res);
    if(res == -1) PyErr_Format(PyExc_ValueError, "error in SegTree f");
    return (bool)res;
}
struct SegTree{
    PyObject_HEAD
    segtree<AutoDecrefPtr, segtree_op, segtree_e>* seg;
    PyObject* op;
    PyObject* e;
    int n;
};

extern PyTypeObject SegTreeType;

static void SegTree_dealloc(SegTree* self){
    delete self->seg;
    Py_DECREF(self->op);
    Py_DECREF(self->e);
    Py_TYPE(self)->tp_free((PyObject*)self);
}
static PyObject* SegTree_new(PyTypeObject* type, PyObject* args, PyObject* kwds){
    SegTree* self;
    self = (SegTree*)type->tp_alloc(type, 0);
    return (PyObject*)self;
}
static inline void set_op_e(SegTree* self){
    segtree_op_py = self->op;
    segtree_e_py = self->e;
}
static int SegTree_init(SegTree* self, PyObject* args){
    if(Py_SIZE(args) != 3){
        self->op = Py_None;  // 何か入れておかないとヤバいことになる
        Py_INCREF(Py_None);
        self->e = Py_None;
        Py_INCREF(Py_None);
        PyErr_Format(PyExc_TypeError, "SegTree constructor expected 3 arguments (op, e, n), got %d", Py_SIZE(args));
        return -1;
    }
    PyObject* arg;
    if(!PyArg_ParseTuple(args, "OOO", &self->op, &self->e, &arg)) return -1;
    Py_INCREF(self->op);
    Py_INCREF(self->e);
    set_op_e(self);
    if(PyLong_Check(arg)){
        int n = (int)PyLong_AsLong(arg);
        if(PyErr_Occurred()) return -1;
        if(n < 0 || n > (int)1e8) {
            PyErr_Format(PyExc_ValueError, "constraint error in SegTree constructor (got %d)", n);
            return -1;
        }
        self->seg = new segtree<AutoDecrefPtr, segtree_op, segtree_e>(n);
        self->n = n;
    }else{
        PyObject *iterator = PyObject_GetIter(arg);
        if(iterator==NULL) return -1;
        PyObject *item;
        vector<AutoDecrefPtr> vec;
        if(Py_TYPE(arg)->tp_as_sequence != NULL) vec.reserve((int)Py_SIZE(arg));
        while(item = PyIter_Next(iterator)) {
            vec.push_back(item);
        }
        Py_DECREF(iterator);
        if (PyErr_Occurred()) return -1;
        self->seg = new segtree<AutoDecrefPtr, segtree_op, segtree_e>(vec);
        self->n = (int)vec.size();
    }
    return 0;
}
static PyObject* SegTree_set(SegTree* self, PyObject* args){
    long p;
    PyObject* x;
    PARSE_ARGS("lO", &p, &x);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree set index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    Py_INCREF(x);
    set_op_e(self);
    self->seg->set((int)p, AutoDecrefPtr(x));
    Py_RETURN_NONE;
}
static PyObject* SegTree_get(SegTree* self, PyObject* args){
    long p;
    PARSE_ARGS("l", &p);
    if(p < 0 || p >= self->n){
        PyErr_Format(PyExc_IndexError, "SegTree get index out of range (size=%d, index=%d)", self->n, p);
        return (PyObject*)NULL;
    }
    PyObject* res = self->seg->get((int)p).p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_prod(SegTree* self, PyObject* args){
    long l, r;
    PARSE_ARGS("ll", &l, &r);
    set_op_e(self);
    auto res = self->seg->prod((int)l, (int)r).p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_all_prod(SegTree* self, PyObject* args){
    PyObject* res = self->seg->all_prod().p;
    return Py_BuildValue("O", res);
}
static PyObject* SegTree_max_right(SegTree* self, PyObject* args){
    long l;
    PARSE_ARGS("lO", &l, &segtree_f_py);
    if(l < 0 || l > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, l=%d)", self->n, l);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->max_right<segtree_f>((int)l);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_min_left(SegTree* self, PyObject* args){
    long r;
    PARSE_ARGS("lO", &r, &segtree_f_py);
    if(r < 0 || r > self->n){
        PyErr_Format(PyExc_IndexError, "SegTree max_right index out of range (size=%d, r=%d)", self->n, r);
        return (PyObject*)NULL;
    }
    set_op_e(self);
    int res = self->seg->min_left<segtree_f>((int)r);
    return Py_BuildValue("l", res);
}
static PyObject* SegTree_to_list(SegTree* self){
    PyObject* list = PyList_New(self->n);
    for(int i=0; i<self->n; i++){
        PyObject* val = self->seg->get(i).p;
        Py_INCREF(val);
        PyList_SET_ITEM(list, i, val);
    }
    return list;
}
static PyObject* SegTree_repr(PyObject* self){
    PyObject* list = SegTree_to_list((SegTree*)self);
    PyObject* res = PyUnicode_FromFormat("SegTree(%R)", list);
    Py_ReprLeave(self);
    Py_DECREF(list);
    return res;
}

static PyMethodDef SegTree_methods[] = {
    {"set", (PyCFunction)SegTree_set, METH_VARARGS, "Set item"},
    {"get", (PyCFunction)SegTree_get, METH_VARARGS, "Get item"},
    {"prod", (PyCFunction)SegTree_prod, METH_VARARGS, "Get item"},
    {"all_prod", (PyCFunction)SegTree_all_prod, METH_VARARGS, "Get item"},
    {"max_right", (PyCFunction)SegTree_max_right, METH_VARARGS, "Binary search on segtree"},
    {"min_left", (PyCFunction)SegTree_min_left, METH_VARARGS, "Binary search on segtree"},
    {"to_list", (PyCFunction)SegTree_to_list, METH_VARARGS, "Convert to list"},
    {NULL}  /* Sentinel */
};
PyTypeObject SegTreeType = {
    PyObject_HEAD_INIT(NULL)
    "atcoder.SegTree",                  /*tp_name*/
    sizeof(SegTree),                    /*tp_basicsize*/
    0,                                  /*tp_itemsize*/
    (destructor)SegTree_dealloc,        /*tp_dealloc*/
    0,                                  /*tp_print*/
    0,                                  /*tp_getattr*/
    0,                                  /*tp_setattr*/
    0,                                  /*reserved*/
    SegTree_repr,                       /*tp_repr*/
    0,                                  /*tp_as_number*/
    0,                                  /*tp_as_sequence*/
    0,                                  /*tp_as_mapping*/
    0,                                  /*tp_hash*/
    0,                                  /*tp_call*/
    0,                                  /*tp_str*/
    0,                                  /*tp_getattro*/
    0,                                  /*tp_setattro*/
    0,                                  /*tp_as_buffer*/
    Py_TPFLAGS_DEFAULT | Py_TPFLAGS_BASETYPE, /*tp_flags*/
    0,                                  /*tp_doc*/
    0,                                  /*tp_traverse*/
    0,                                  /*tp_clear*/
    0,                                  /*tp_richcompare*/
    0,                                  /*tp_weaklistoffset*/
    0,                                  /*tp_iter*/
    0,                                  /*tp_iternext*/
    SegTree_methods,                    /*tp_methods*/
    0,                                  /*tp_members*/
    0,                                  /*tp_getset*/
    0,                                  /*tp_base*/
    0,                                  /*tp_dict*/
    0,                                  /*tp_descr_get*/
    0,                                  /*tp_descr_set*/
    0,                                  /*tp_dictoffset*/
    (initproc)SegTree_init,             /*tp_init*/
    0,                                  /*tp_alloc*/
    SegTree_new,                        /*tp_new*/
    0,                                  /*tp_free*/
    0,                                  /*tp_is_gc*/
    0,                                  /*tp_bases*/
    0,                                  /*tp_mro*/
    0,                                  /*tp_cache*/
    0,                                  /*tp_subclasses*/
    0,                                  /*tp_weaklist*/
    0,                                  /*tp_del*/
    0,                                  /*tp_version_tag*/
    0,                                  /*tp_finalize*/
};

static PyModuleDef atcodermodule = {
    PyModuleDef_HEAD_INIT,
    "atcoder",
    NULL,
    -1,
};

PyMODINIT_FUNC PyInit_atcoder(void)
{
    PyObject* m;
    if(PyType_Ready(&SegTreeType) < 0) return NULL;

    m = PyModule_Create(&atcodermodule);
    if(m == NULL) return NULL;

    Py_INCREF(&SegTreeType);
    if (PyModule_AddObject(m, "SegTree", (PyObject*)&SegTreeType) < 0) {
        Py_DECREF(&SegTreeType);
        Py_DECREF(m);
        return NULL;
    }

    return m;
}
"""
code_setup = r"""
from distutils.core import setup, Extension
module = Extension(
    "atcoder",
    sources=["atcoder_library_wrapper.cpp"],
    extra_compile_args=["-O3", "-march=native", "-std=c++14"]
)
setup(
    name="atcoder-library",
    version="0.0.1",
    description="wrapper for atcoder library",
    ext_modules=[module]
)
"""

import os
import sys
if sys.argv[-1] == "ONLINE_JUDGE" or os.getcwd() != "/imojudge/sandbox":
    with open("atcoder_library_wrapper.cpp", "w") as f:
        f.write(code_segtree)
    with open("setup.py", "w") as f:
        f.write(code_setup)
    os.system(f"{sys.executable} setup.py build_ext --inplace")

from atcoder import SegTree
from operator import itemgetter

class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

op = lambda a, b: a if a > b else b
e = 0
seg = SegTree(op, e, N)
f = lambda x: x == 0
uf = UnionFind(N)
for _, _, y in IXY:
    l = seg.min_left(y, f) - 1
    if l >= 0:
        uf.unite(l, y)
    seg.set(y, 1)
    #print(seg, l)
#print()
seg = SegTree(op, e, N)
for _, _, y in IXY[::-1]:
    r = seg.max_right(y, f)
    if r < N:
        uf.unite(r, y)
    seg.set(y, 1)
    #print(seg, r)

Ans = [-100] * N
for i, x, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
# input here
_INPUT = """\
7
6 4
4 3
3 5
7 1
2 7
5 2
1 6
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N = int(input())
    xy = [list(map(int, input().split())) for i in range(N)]

    dp = [0] * (N)
    visited = [] 
    count = 0

    for j in range(len(xy)):
        vis = []
        for i in range(1,len(xy)-j):
            if (xy[j][0] > xy[j+i][0])&(xy[j][1] > xy[j+i][1]):
                vis.append(j+i)
            elif (xy[j][0] < xy[j+i][0])&(xy[j][1] < xy[j+i][1]):
                vis.append(j+i)
        visited.append(vis)

    for k in range(len(visited)):
        dp[k] += (len(visited[k])+1)
        for l in range(len(visited[k])):
            dp[visited[k][l]] += len(visited[k])

    for x in dp:
        print(x)
            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
L = []
for _ in range(N):
  M = list(map(int,input().split())) + [_ + 1]
  L.append(M)
L.sort()

class union_find():
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

    def find_root(self,x):
        if self.root[x]<0:
            return x
        else:
            self.root[x]=self.find_root(self.root[x])
            return self.root[x]

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)
        

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def same(self,x,y):
        return self.find_root(x)==self.find_root(y)

    def cnt(self,x):
        return -self.root[self.find_root(x)]
g = union_find(N)
for i in range(N-1):
  for j in range(i,N):
    if L[i][1] < L[j][1]:
      a = L[i][2]
      b = L[j][2]
      g.unite(a,b)

for k in range(1,N+1):
  if g.root[k] > 0:
    print(-g.root[g.root[k]])
  else:
    print(-g.root[k])

Submission status: Wrong Answer

Solution code:

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)
        self.size[0] = 0

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        self.leader(self[x])
        self.leader(self[y])
        return  self[x] == self[y]

    def leader(self,x):
        if self.root[x] == x:
            return x
        else:
            self.root[x] = self.leader(self.root[x])
            return self.root[x]


    def get_size(self,k):
        return self.size[k]

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]


uf = UnionFind(N)
merge = uf.merge
same = uf.same
get_size = uf.get_size

for i in range(1,N+1):
    curx, cury = XY[i-1]
    for j in range(i,N+1):
        if uf.root[i] == uf.root[j]:
            continue
        if curx < XY[j-1][0] and cury < XY[j-1][1]:
            merge(i,j)
        elif curx > XY[j-1][0] and cury > XY[j-1][1]:
            merge(i,j)

for k in range(1,N+1):
    print(get_size(uf.root[k]))

Submission status: Wrong Answer

Solution code:
n=input()
a=[[int(i)-1 for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]
a.sort()
l=[i for i in range(n)]
r=[0 for i in range(n)]
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
s=[0]
for i in range(1,n):
    while len(s)!=0 and a[i][1]<a[s[-1]][1]:
        s.pop()
    if len(s)!=0:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    s.append(i)
s=[n-1]
for i in range(n-2,-1,-1):
    while len(s)!=0 and a[i][1]>a[s[-1]][1]:
        s.pop()
    if len(s)!=0:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    s.append(i)
o=[find(i) for i in range(n)]
d={}
for i in o:
    d[i]=d.get(i,0)+1
for i  in range(n):
    print d[o[c[i]]]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

sa = sorted([(a[i], i) for i in range(N)])
uf = UnionFind(N)
table = [a[sa[i][1]][1] for i in range(N)]
mxtable = [0] * N
mxtable[-1] = table[-1]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] >= mxtable[i]: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
  #print(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] <= mntable[i]: ok = m
    else: ng = m
  #print(i, ok)
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
for i in range(N): print(uf.Count(i))

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
dp=[[0 for _ in range(n)] for _ in range(n)]
cords=[]
for i in range(n):
    x,y=map(int,input().split())
    dp[x-1][y-1]=1
    cords.append((x-1,y-1))

dp=np.asarray(dp)

for x,y in cords:
    print(np.sum(dp[x+1:,y+1:])+np.sum(dp[:x,:y])+1)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())

XY = [list(map(int, input().split())) + [i] for i in range(n)]
XY.sort()


class UnionFind:
    # あり本実装
    # rankとrootの配列を1つで賄う方法
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

    # 根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 同じかどうかの判定
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

    # 　2つの集合の合体
    # 重みが大きい方に小さい方をつけるようにする
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


UF = UnionFind(n)
ans = [0] * (n)
saisho_val = n + 5
saisho_idx = -1
memo = [n + 1] * (n)

for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1

    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] < y:
                ok = mid
            else:
                ng = mid
        for num in reversed(range(ok, x)):
            if UF.is_same(num, x):
                break
            UF.unite(num, x)
        # print("u", x, saisho_idx)
    memo[i] = saisho_val

for i in range(n):
    x, _, idx = XY[i]
    ans[idx] = abs(UF.size(i))
print("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N = I()
A = [0]*N
for i in range(N):
    x,y = MI()
    A[x-1] = (y,i)


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
        self.X = [1]*(n+1)

    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)

    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.X[x] += self.X[y]


class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = 1 << (N-1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])

    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
            i >>= 1

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)

    def max_right(self,l,z):  # [l,r-1] で True,[l,r] で False たる r
        if l >= self.N:
            return self.N
        l += self.N
        s = self.unit
        while True:
            while l % 2 == 0:
                l >>= 1
            if not z(self.func(s,self.tree[l])):
                while l < self.N:
                    l *= 2
                    if z(self.func(s, self.tree[l])):
                        s = self.func(s, self.tree[l])
                        l += 1
                return l - self.N
            s = self.func(s, self.tree[l])
            l += 1
            if l & -l == l:
                break
        return self.N

    def min_left(self,r,z):  # [l,r-1] で True,[l-1,r-1] で False たる l
        if r <= 0:
            return 0
        r += self.N
        s = self.unit
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.func(self.tree[r], s)):
                while r < self.N:
                    r = r*2+1
                    if z(self.func(self.tree[r], s)):
                        s = self.func(self.tree[r], s)
                        r -= 1
                return r + 1 - self.N
            s = self.func(self.tree[r], s)
            if r & -r == r:
                break
        return 0


UF = UnionFind(N)
seg = SegTree(N+1,min,10**9)
for j in range(1,N+1):
    a,i = A[j-1]
    seg.set_val(a,j)
    m = seg.fold(0,a)
    if m == 10**9:
        continue
    else:
        if not UF.same_check(m,j):
            UF.unite(m,j)

seg2 = SegTree(N+1,max,0)
for j in range(N,0,-1):
    a,i = A[j-1]
    seg2.set_val(a,j)
    M = seg2.fold(a+1,N+1)
    if M == 0:
        continue
    else:
        if not UF.same_check(M,j):
            UF.unite(M,j)


ANS = [0]*N
for j in range(N):
    a,i = A[j]
    ANS[i] = UF.X[UF.find(j+1)]

print(*ANS,sep='\n')