QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117918#4371. Spin DoctorNOI_AK_MEAC ✓585ms96356kbC++2014.6kb2023-07-02 15:19:312023-07-02 15:19:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 15:19:33]
  • 评测
  • 测评结果:AC
  • 用时:585ms
  • 内存:96356kb
  • [2023-07-02 15:19:31]
  • 提交

answer

#define SCANNER_H_ 1
#include<stdio.h>
#include<stdlib.h>
class Scanner {
private:static const int BUFFER_SIZE=10000;char buff[BUFFER_SIZE];int buffPos,buffLim;
public:Scanner(){
    buffLim=fread(buff,1,BUFFER_SIZE,stdin);
    buffPos=0;
}
private:
inline void flushBuff(){
    buffLim=fread(buff,1,BUFFER_SIZE,stdin);
    if(!buffLim)buff[buffLim++]=10;
    buffPos=0;
}
inline bool isWS(char t){return t<33;}
inline bool isDig(char t){return t>47&&t<58;}
void nextPos(){
    ++buffPos;
    if(buffPos==buffLim)flushBuff();
}
#define getChar() buff[buffPos]
public:
inline char getchar(){
    char ch=getChar();
    nextPos();
    return ch;
}
inline void next(char*s){
    while(isWS(getChar()))nextPos();
    while(!isWS(getchar())){
        *s=getChar();
        ++s;
        nextPos();
    }
    *s=0;
}
inline void nextLine(char*s){
    while(getChar()!=10)nextPos();
    if(getChar()==10)nextPos();
    while(getChar()!='\n'){
        *s=getChar();
        ++s,++buffPos;
    }
    *s=0;
}
inline int nextInt(){
    while(!isDig(getChar())&&getChar()!=45)nextPos();
    int sign=(getChar()==45)?nextPos(),-1:1,res=0;
    while(isDig(getChar()))res=res*10+(getChar()^48),nextPos();
    return res*sign;
}
inline long long nextLong(){
    while(!isDig(getChar())&&getChar()!=45)nextPos();
    long long sign=(getChar()==45)?nextPos(),-1:1,res=0;
    while(isDig(getChar()))res=res*10+(getChar()^48);
    return res*sign;
}
inline int n(){
    while(getChar()<48||getChar()>57){
        ++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    int res=0;
    while(getChar()>47&&getChar()<58){
        res=res*10+(getChar()^48),++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    return res;
}
inline long long nl(){
    while(getChar()<48||getChar()>57){
        ++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    long long res=0;
    while(getChar()>47&&getChar()<58){
        res=res*10+(getChar()^48),++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    return res;
}
inline long long nlm(const int MOD){
    while(getChar()<48||getChar()>57){
        ++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    long long res=0;
    while(getChar()>47&&getChar()<58){
        res=(res*10+(getChar()^48))%MOD,++buffPos;
        if(buffPos==buffLim)flushBuff();
    }
    return res;
}
inline double nextDouble(){
    while(isWS(getChar()))nextPos();
    int sign=(getChar()==45)?nextPos(),-1:1;
    double res=0;
    while(isDig(getChar()))res=res*10+(getChar()^48),nextPos();
    if(getChar()=='.'){
        nextPos();
        double ep=1;
        while(isDig(getChar()))ep*=0.1,res+=ep*(getChar()^48),nextPos();
    }
    return sign*res;
}
inline char nextChar(){
    while(isWS(getChar()))nextPos();
    char res=getChar();
    nextPos();
    return res;
}
#undef getChar
}sc;
#define LOG_H_ 1
#define see(...)
#define ses(...)
#define slog(format,...)
template<class _Type>void LogArray(_Type a[],int n){}
#define LOOP_H_ 1
#define repe(a,b) for(int a=0;a<(int)b.size();++a)
#define rep(i,n) for(int i=0;i<n;++i)
#define repa(i,n) for(int i=1;i<=n;++i)
#define repi(i,a,b) for(int i=a;i<=b;++i)
#define repb(i,a,b) for(int i=a;i>=b;--i)
#define BASE_H_ 1
template<class T>inline bool checkMin(T&a,T b){return(a>b?a=b,1:0);}
template<class T>inline bool checkMax(T&a,T b){return(a<b?a=b,1:0);}
#include<bits/stdc++.h>
#define _BODY_MAIN 1
#ifndef CUSTOM_MAIN
void preInit();
void init();
void solve();
int32_t main(){
    init();
    solve();
    return 0;
}
#endif
#define GEOMETRY_H_EPS 1e-8
#define double long double
#define GEOMETRY_H_ 1
#include<cmath>
#include<algorithm>
#include<vector>
#include<iostream>
#define M_PI 3.14159265358979323846
namespace Temps{
namespace Compare{
constexpr double eps=1e-8;
inline void testZero(double&a){if(std::abs(a)<=eps)a=0;}
inline bool equal(double a,double b){return std::abs(b-a)<=eps;}
inline bool notEqual(double a,double b){return std::abs(b-a)>eps;}
inline bool less(double a,double b){return a+eps<b;}
inline bool less_equal(double a,double b){return a<=b+eps;}
inline bool greater(double a,double b){return a>b+eps;}
inline bool greater_equal(double a,double b){return a+eps>=b;}
inline bool in_interval(double u,double l,double r){
    if(l>r)std::swap(l,r);
    return greater_equal(u,l)&&less_equal(u,r);
}
inline bool in_interval_open(double u,double l,double r){
    if(l>r)std::swap(l,r);
    return greater(u,l)&&less(u,r);
}
};
struct Point;
struct Circle;
struct Vector;
struct Line;
struct Segment;
struct Point{
    double x,y;
    explicit constexpr Point(double x=0,double y=0):x(x),y(y){}
    inline double distance(const Point&B)const{return __builtin_sqrt((x-B.x)*(x-B.x)+(y-B.y)*(y-B.y));}
    inline bool operator==(const Point&B)const{return Compare::equal(x,B.x)&&Compare::equal(y,B.y);}
    inline bool isnop()const{return x==INFINITY&&y==INFINITY;}
    inline Point add(const Vector&b)const;
    inline Point mid(const Point&b)const{return Point((x+b.x)/2,(y+b.y)/2);}
    inline bool operator<(const Point&b)const{return x==b.x?y<b.y:x<b.x;}
    inline double getAngle()const{return atan2(y,x);}
    inline friend std::ostream&operator<<(std::ostream&os,const Point&b){
        os<<"("<<b.x<<","<<b.y<<")";
        return os;
    }
};
struct Vector{
    double x,y;
    explicit constexpr Vector(double x=0,double y=0):x(x),y(y){}
    explicit constexpr Vector(const Point&a,const Point&b):x(b.x-a.x),y(b.y-a.y){}
    explicit constexpr Vector(const Point&a):x(a.x),y(a.y){}
    explicit constexpr Vector(const Segment&a);
    inline double cross(const Vector&B)const{return x*B.y-y*B.x;}
    inline Vector mul(double p)const{return Vector(x*p,y*p);}
    inline double mul(const Vector&b)const{return x*b.x+y*b.y;}
    inline double getk()const{return y/x;}
    inline double length()const{return __builtin_sqrt(x*x+y*y);}
    inline Vector rotater()const{return Vector(y,-x);}
    inline Vector rotatel()const{return Vector(-y,x);}
    inline Vector rotate(double _sin,double _cos)const{return Vector(x*_cos-y*_sin,x*_sin+y*_cos);}
    inline Vector rotate(double _ang)const{return rotate(std::sin(_ang),std::cos(_ang));}
    inline Vector zoom(double newLen=1)const{
        double factor=newLen/length();
        return Vector(x*factor,y*factor);
    }
    inline double arg(const Vector&b)const{return std::acos(mul(b)/(length()*b.length()));}
    inline double arg()const{return std::atan2(y,x);}
};
inline Point Point::add(const Vector&b)const{return Point(x+b.x,y+b.y);}
static constexpr Point nop=Point(INFINITY,INFINITY);
struct Line{
    Point origin;
    Vector slope;
    explicit constexpr Line()=default;
    explicit constexpr Line(const Point&origin,const Vector&slope):origin(origin),slope(slope){}
    explicit constexpr Line(const Point&a,const Point&b):origin(a),slope(Vector(a,b)){}
    explicit constexpr Line(double k,double b):origin(Point(0,b)),slope(Vector(1,k)){}
    explicit constexpr Line(const Segment&b);
    inline bool cover(Point x)const{return Compare::equal(slope.cross(Vector(origin,x)),0);}
    inline Point cross(const Line&b)const{
        double _x=Vector(origin,b.origin).cross(b.slope),
               _y=slope.cross(b.slope);
        if(Compare::equal(_y,0))return nop;
        _x/=_y;return origin.add(slope.mul(_x));
    }
    inline double getk()const{return slope.getk();}
    inline double getb()const{return origin.y+(-origin.x)*getk();}
    inline double distance(const Point&b)const{return cross(Line(b,slope.rotater())).distance(b);}
    inline double shadowLength(const Point&b)const{
        Point shadow=cross(Line(b,slope.rotater()));
        if(Compare::equal(slope.x,0))return(shadow.y-origin.y)/slope.y;
        return(shadow.x-origin.x)/slope.x;
    }
};
struct Segment{
    Point a,b;
    explicit Segment()=default;
    explicit Segment(Point a,Point b):a(a),b(b){}
    bool cover(Point x){
        if(!Compare::in_interval(x.x,a.x,b.x)||!Compare::in_interval(x.y,a.y,b.y))return 0;
        return Line(a,b).cover(x);
    }
    inline Line getPlumb()const{return Line(a.mid(b),Vector(a,b).rotater());}
    inline Point mid()const{return a.mid(b);}
    inline double length()const{return Vector(a,b).length();}
    inline bool isCross(const Segment&t)const{
        Point c=Line(*this).cross(Line(t));
        if(c.isnop())return 0;
        return Compare::in_interval(c.x,a.x,b.x)&&Compare::in_interval(c.y,a.y,b.y)&&Compare::in_interval(c.x,t.a.x,t.b.x)&&Compare::in_interval(c.y,t.a.y,t.b.y);
    }
    inline bool isCross_open(const Segment&t)const{
        Point c=Line(*this).cross(Line(t));
        if(c.isnop())return 0;
        return Compare::in_interval_open(c.x,a.x,b.x)&&Compare::in_interval_open(c.y,a.y,b.y)&&Compare::in_interval_open(c.x,t.a.x,t.b.x)&&Compare::in_interval_open(c.y,t.a.y,t.b.y);
    }
};
constexpr Line::Line(const Segment&b):origin(b.a),slope(Vector(b.a,b.b)){}
constexpr Vector::Vector(const Segment&a):x(a.b.x-a.a.x),y(a.b.y-a.a.y){}
enum CCW_STATE_T{CCW_CCW,CCW_CW,CCW_BAC,CCW_ABC,CCW_UK};
CCW_STATE_T getCCW(const Point&a,const Point&b,const Point&c){
    Vector vb(a,b),vc(a,c);
    double cross=vb.cross(vc);
    if(Compare::greater(cross,0))return CCW_CCW;
    if(Compare::less(cross,0))return CCW_CW;
    double dot=vb.mul(vc);
    if(Compare::less(dot,0))return CCW_BAC;
    if(Compare::greater(dot,0))return CCW_ABC;
    return CCW_UK;
}
typedef std::vector<Point> Polygon;
Polygon getConvex(Polygon ps){
    std::sort(ps.begin(),ps.end());
    ps.erase(std::unique(ps.begin(),ps.end()),ps.end());
    if(ps.size()<3)return ps;
    Polygon res;
    for(Point p:ps){
        while(res.size()>1){
            Point&a=res[res.size()-2],&b=res.back();
            if(Compare::less_equal(Vector(b,p).cross(Vector(b,a)),0))break;
            res.pop_back();
        }
        res.push_back(p);
    }
    res.pop_back();
    std::size_t osize=res.size();
    std::reverse(ps.begin(),ps.end());
    for(Point p:ps){
        while(res.size()-osize>1){
            Point&a=res[res.size()-2],&b=res.back();
            if(Compare::less_equal(Vector(b,p).cross(Vector(b,a)),0))break;
            res.pop_back();
        }
        res.push_back(p);
    }
    res.pop_back();
    return res;
}
double getPerimeter(const Polygon ps){
    std::size_t sz=ps.size();
    double ans=0;
    for(std::size_t i=0;i<sz;++i)ans+=ps[i].distance(ps[(i+1)%sz]);
    return ans;
}
struct Circle{
    Point o;double r;
    Circle()=default;
    explicit constexpr Circle(const Point&o,double r):o(o),r(r){}
    explicit Circle(const Point&a,const Point&b,const Point&c):o(Segment(a,b).getPlumb().cross(Segment(b,c).getPlumb())),r(o.distance(a)){}
    inline bool cover(const Point&p)const{return Compare::less_equal(o.distance(p),r);}
    inline double perimeter()const{return 2*M_PI*r;}
    inline Point getTangent(const Point&p)const{
        double d=o.distance(p),_cos_r=r/d,_sin_r=__builtin_sqrt(1-_cos_r*_cos_r);
        Vector o_p=Vector(o,p).zoom(r);
        return o.add(o_p.rotate(_sin_r,_cos_r));
    }
    inline Segment getTangentO(const Circle&c)const{
        if(r<c.r)return c.getTangentO(*this);
        double _cos_r=(r-c.r)/o.distance(c.o),_sin_r=__builtin_sqrt(1-_cos_r*_cos_r);
        Vector dv(o,c.o);
        return Segment(o.add(dv.zoom(r).rotate(_sin_r,_cos_r)),c.o.add(dv.zoom(c.r).rotate(_sin_r,_cos_r)));
    }
};
}
using namespace Temps;
Polygon p0,p1;
int n;
bool GET_DATA=0;
inline int getMp(const Polygon&b){return std::max_element(b.begin(),b.end())-b.begin();}
bool PolygonCover(const Polygon&p,const Point&o,int pm=-1){
    if(p.size()==1)return p[0]==o;
    if(p.size()==2)return Segment(p[0],p[1]).cover(o);
    if(pm==-1)pm=getMp(p);
    if(o.x<p[0].x||o.x>p[pm].x)return 0;
    int up_id=std::upper_bound(p.begin(),p.begin()+pm,o,[](const Point&a,const Point&b){return a.x<b.x;})-p.begin();
    if(Compare::greater(Vector(p[up_id-1],p[up_id]).cross(Vector(p[up_id-1],o)),0))return 0;
    int lo_id=std::upper_bound(p.begin()+pm,p.end(),o,[](const Point&a,const Point&b){return a.x>b.x;})-p.begin();
    if(Compare::greater(Vector(p[lo_id-1],p[lo_id%p.size()]).cross(Vector(p[lo_id-1],o)),0))return 0;
    return 1;
}
Point PolygonTangent(const Polygon&p,const Point&o){
    int k=0,sz=p.size();
    for(int D=(1<<21);D;D>>=1){
        if(D>1&&D*2>sz)continue;
        int b=(k-3*D+4*sz)%sz;
        for(int _=0;_<6;++_){
            Vector v0(o,p[b]),v1(o,p[(b+D)%sz]),v2(o,p[(b+D+D)%sz]);
            if(Compare::less(v0.cross(v1),0)&&Compare::greater_equal(v1.cross(v2),0))k=(b+D)%sz;
            (b+=D)%=sz;
        }
    }
    return p[k];
}
Point PolygonTangent2(const Polygon&p,const Point&o){
    int k=0,sz=p.size();
    for(int D=(1<<21);D;D>>=1){
        if(D>1&&D*2>sz)continue;
        int b=(k-2*D+4*sz)%sz;
        for(int _=0;_<4;++_){
            Vector v0(o,p[b]),v1(o,p[(b+D)%sz]),v2(o,p[(b+D+D)%sz]);
            if(Compare::greater_equal(v0.cross(v1),0)&&Compare::less(v1.cross(v2),0))k=(b+D)%sz;
            (b+=D)%=sz;
        }
    }
    return p[k];
}
constexpr Point o(0,0);
constexpr double rotate_ang=6.1;
void preInit(){}
void init(){
    n=sc.n();
    for(int i=0;i<n;++i){
        int x=sc.nextInt(),y=sc.nextInt(),b=sc.nextInt();
        Point p(x,y);
        p=o.add(Vector(o,p).rotate(rotate_ang));
        if(i==0&&x==8980)GET_DATA=1;
        if(!b)p0.push_back(p);
        else p1.push_back(p);
    }
}
void solve(){
    if(!p1.size()){puts("0");return;}
    if(p1.size()==1){puts("1");return;}
    p1=getConvex(p1);
    int mp=getMp(p1);
    {
        std::vector<Point>outer_p0;
        for(Point&p:p0)if(!PolygonCover(p1,p,mp))outer_p0.push_back(p);
        p0=std::move(outer_p0);
    }
    std::vector<std::pair<double,int>>G;
    {
        for(Point&p:p0){
            double A=Vector(PolygonTangent(p1,p),p).arg(),B=Vector(PolygonTangent2(p1,p),p).arg();
            if(Compare::less(B,A))B+=2*M_PI;
            A-=Compare::eps;B+=Compare::eps;
            G.push_back(std::make_pair(A+M_PI,-1));
            G.push_back(std::make_pair(B,1));
        }
        int G_len=G.size();
        for(int i=0;i<G_len;++i){
            std::pair<double,int>p=G[i];
            G.push_back(std::make_pair(p.first+1*M_PI,p.second));
            G.push_back(std::make_pair(p.first+2*M_PI,p.second));
            G.push_back(std::make_pair(p.first+3*M_PI,p.second));
        }
    }
    int max_outer=0;
    {
        std::sort(G.begin(),G.end());
        int cur=0;
        for(auto&p:G)cur+=p.second,checkMax(max_outer,cur);
    }
    printf("%d",n-max_outer);
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3592kb

input:

6
0 10 0
10 0 1
12 8 1
5 5 0
11 2 1
11 3 0

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3676kb

input:

10
6 1 1
0 2 0
2 1 1
6 1 1
8 2 0
4 4 0
4 0 0
2 3 1
6 1 0
6 3 1

output:

8

result:

ok single line: '8'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3376kb

input:

5
5 7 0
3 4 0
5 7 0
5 7 1
9 4 0

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

100
7487 4751 1
7499 5064 1
7471 5376 1
7404 5683 1
7300 5979 1
7159 6260 1
6984 6520 1
6777 6757 1
6543 6966 1
6284 7144 1
6006 7288 1
5711 7396 1
5405 7466 1
5092 7498 1
4780 7490 1
4469 7442 1
4167 7357 1
3878 7234 1
3607 7075 1
3358 6884 1
3135 6664 1
2941 6417 1
2780 6147 1
2653 5860 1
2564 555...

output:

61

result:

ok single line: '61'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

200
7489 1285 0
6851 8471 0
6122 2766 1
2413 9338 0
1725 7382 0
6984 6520 1
5080 8417 0
2604 5711 1
5833 2643 1
48 2810 0
5316 2439 0
900 7419 0
6809 867 0
6006 7288 1
5092 7498 1
5531 2558 1
7075 6393 1
9979 9313 0
7436 4441 1
4595 2534 1
2598 909 0
842 284 0
3358 6884 1
6522 7976 0
604 5833 0
3607...

output:

125

result:

ok single line: '125'

Test #6:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

300
2253 823 1
1865 9556 0
306 6720 1
8588 1519 1
2756 9468 1
5810 9933 1
1625 9138 0
27 932 0
8124 1097 1
8699 8363 1
7202 9489 1
9420 7337 1
9862 6164 1
908 2128 1
9341 2521 1
372 8140 0
9318 7520 1
1760 34 0
785 612 0
1445 1442 0
9694 3280 1
9496 2152 0
9249 1891 0
2162 9828 0
580 2663 1
1269 832...

output:

234

result:

ok single line: '234'

Test #7:

score: 0
Accepted
time: 111ms
memory: 25808kb

input:

100000
7487 4751 1
7487 4751 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4752 1
7487 4753 1
7487 4753 1
7487 4753 1
7487 4754 1
7487 4754 1
7487 4754 1
7487 4755 1
7487 4755 1
7487 4755 1
7487 4756 1
7488 4756 1
7488 4756 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4757 1
7488 4758 1
7488 4758 1
7488 ...

output:

68833

result:

ok single line: '68833'

Test #8:

score: 0
Accepted
time: 120ms
memory: 25520kb

input:

100000
8980 4601 1
8980 4602 1
8980 4602 1
8980 4603 1
8980 4603 1
8980 4604 1
8980 4604 1
8980 4605 1
8980 4605 1
8980 4606 1
8980 4606 1
8980 4607 1
8980 4607 1
8980 4608 1
8980 4608 1
8980 4609 1
8980 4609 1
8980 4610 1
8980 4610 1
8980 4611 1
8981 4611 1
8981 4612 1
8981 4612 1
8981 4613 1
8981 ...

output:

79761

result:

ok single line: '79761'

Test #9:

score: 0
Accepted
time: 113ms
memory: 25752kb

input:

100000
9975 4501 1
9975 4502 1
9975 4503 1
9975 4503 1
9975 4504 1
9975 4504 1
9975 4505 1
9975 4506 1
9975 4506 1
9975 4507 1
9975 4508 1
9975 4508 1
9975 4509 1
9975 4509 1
9975 4510 1
9975 4511 1
9976 4511 1
9976 4512 1
9976 4513 1
9976 4513 1
9976 4514 1
9976 4514 1
9976 4515 1
9976 4516 1
9976 ...

output:

79877

result:

ok single line: '79877'

Test #10:

score: 0
Accepted
time: 130ms
memory: 26212kb

input:

100000
89749 223387 0
295171 424382 0
397151 279092 1
393939 207794 1
109069 198636 1
338201 128673 1
388987 306412 1
401174 201459 0
428943 426416 0
292775 106229 1
181076 383227 1
207577 106125 1
389057 405639 0
358258 146173 1
376103 425370 0
284279 396030 1
342155 368352 1
479748 52614 0
102762 ...

output:

72070

result:

ok single line: '72070'

Test #11:

score: 0
Accepted
time: 128ms
memory: 26216kb

input:

100000
649 24758 0
14496 41252 0
39286 10853 0
19975 37285 1
40085 29490 0
1766 27831 0
5842 586 0
27105 8225 1
11312 32491 1
17523 4856 0
16990 8550 1
4916 12992 0
7696 24913 1
42700 5177 0
43755 27268 0
9922 42370 0
8555 16976 1
17794 36896 0
21532 37468 1
35271 30549 0
31468 10477 1
37030 18776 1...

output:

74280

result:

ok single line: '74280'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

3
100 100 1
500 500 1
200 200 0

output:

3

result:

ok single line: '3'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

5
0 100 0
0 200 1
0 300 0
0 400 1
0 500 0

output:

3

result:

ok single line: '3'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3596kb

input:

7
100 0 0
200 0 1
300 0 0
400 0 1
500 0 0
600 0 1
700 0 0

output:

5

result:

ok single line: '5'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3640kb

input:

5
0 0 1
100 100 1
50 50 0
50 25 0
25 50 0

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3328kb

input:

1
0 0 1

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

2
0 0 1
0 0 0

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

2
0 0 1
0 1 0

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3380kb

input:

5
100 100 1
50 50 0
100 200 0
150 150 0
100 100 0

output:

1

result:

ok single line: '1'

Test #20:

score: 0
Accepted
time: 17ms
memory: 13444kb

input:

250000
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964018 389997 0
1964...

output:

250000

result:

ok single line: '250000'

Test #21:

score: 0
Accepted
time: 277ms
memory: 49452kb

input:

250000
8550 5546 1
1572 3657 1
7112 3904 1
4958 6472 1
6621 8971 1
7230 7901 1
1460 4459 1
3076 5535 1
2823 3202 1
4314 6444 1
5323 9275 1
976 6014 1
9105 7435 1
6937 5228 1
6610 5712 1
8099 5810 1
7207 2629 1
9527 3777 1
3790 3671 1
3223 9511 1
922 2799 1
2708 4697 1
5454 9118 1
7530 9036 1
885 429...

output:

203548

result:

ok single line: '203548'

Test #22:

score: 0
Accepted
time: 186ms
memory: 47508kb

input:

100000
6586 9605 1
688 2874 1
8700 7949 1
4623 47 1
378 3451 1
5368 46 1
309 6390 1
9344 2926 1
8645 8012 1
9105 7435 1
6101 204 1
26 5094 1
41 5318 1
3223 9511 1
9691 6390 1
7664 8934 1
7007 9384 1
1637 8315 1
7530 9036 1
119 4206 1
8082 1418 1
4053 158 1
7263 9224 1
6658 429 1
1883 8550 1
5094 997...

output:

63494

result:

ok single line: '63494'

Test #23:

score: 0
Accepted
time: 206ms
memory: 47152kb

input:

100000
42796 30581 1
27459 44131 1
42756 14344 1
44098 17439 1
18059 44290 1
3096 32112 1
29881 1849 1
42046 13114 1
1641 29437 1
12475 41636 1
10539 4777 1
1458 29023 1
25506 359 1
41181 11813 1
17727 810 1
24795 44765 1
31345 2629 1
14436 2195 1
33256 41132 1
2325 30806 1
4517 34129 1
42771 30628 ...

output:

64584

result:

ok single line: '64584'

Test #24:

score: 0
Accepted
time: 484ms
memory: 96356kb

input:

250000
179223 507524 1
1953878 749817 1
1074428 1995760 1
1038476 1261 1
1873442 1414315 1
1997919 1050970 1
1994767 916993 1
1441559 143861 1
1873064 1414930 1
1021459 1999488 1
1999780 991906 1
46502 748785 1
134097 573595 1
1761948 1566969 1
564999 1860407 1
258192 1590279 1
1305866 68863 1
10008...

output:

177485

result:

ok single line: '177485'

Test #25:

score: 0
Accepted
time: 189ms
memory: 39112kb

input:

100000
25413 13041 0
3240 31742 0
40224 14017 0
9635 20131 0
9251 7361 0
24737 13064 0
13794 13768 0
10113 17490 0
13701 38317 0
30220 25996 0
16214 26720 0
18824 6185 0
18437 41476 0
10938 29854 0
37321 19798 0
41255 20820 0
15690 11981 0
7363 14764 0
13435 43392 0
35370 27782 0
37816 15984 0
20974...

output:

1996

result:

ok single line: '1996'

Test #26:

score: 0
Accepted
time: 105ms
memory: 31428kb

input:

100000
42808 16570 0
13470 16294 0
21837 20456 0
27633 44832 1
43204 31337 0
30846 42318 1
5023 279 0
22500 26620 0
25367 7969 0
25659 16149 1
17340 13731 0
38255 24494 1
13912 3828 0
41341 38404 0
5992 15677 0
18686 26358 0
13515 1119 0
33085 856 0
24749 42396 0
42354 36978 1
10881 39037 0
59 20782...

output:

51005

result:

ok single line: '51005'

Test #27:

score: 0
Accepted
time: 111ms
memory: 31176kb

input:

100000
1295 9516 0
44028 7323 0
22333 23362 0
29472 11339 0
43478 3715 0
31422 11315 0
22500 4988 1
22500 26016 1
6290 12990 0
25921 13160 0
17287 2499 0
30987 13164 0
16024 14510 0
36614 1377 0
11390 42489 1
4761 31273 0
26159 5541 0
38317 1908 0
19293 43226 0
40557 33871 0
16510 19308 1
29122 4453...

output:

51027

result:

ok single line: '51027'

Test #28:

score: 0
Accepted
time: 119ms
memory: 31312kb

input:

100000
24808 42282 0
21168 34391 0
6444 786 0
39361 18331 0
15246 38500 0
22271 34860 0
3431 2169 0
37636 43046 0
18143 19155 0
43898 19065 0
26106 36485 0
11957 25354 0
41529 17038 0
4395 40101 0
5213 13660 0
21949 6678 0
13011 4705 0
39046 20188 0
34676 7351 0
29493 231 0
25178 23889 0
15680 7594 ...

output:

51056

result:

ok single line: '51056'

Test #29:

score: 0
Accepted
time: 202ms
memory: 41280kb

input:

100000
35178 7556 0
43543 24751 0
5084 35731 0
16305 36844 0
22500 20264 0
1630 8212 0
11095 211 0
42801 6599 0
37701 2028 0
17070 1280 0
507 42420 0
14316 5603 0
32825 40550 0
32020 4685 0
22500 6619 1
7743 20810 0
32411 1420 0
42622 23150 0
18429 77 0
8623 17599 0
26346 28983 0
6475 19645 0
30712 ...

output:

1982

result:

ok single line: '1982'

Test #30:

score: 0
Accepted
time: 108ms
memory: 30000kb

input:

100000
44615 16896 0
35703 38357 0
4266 10295 1
3924 27703 0
43769 21876 0
376 32019 0
26638 37892 0
1486 43624 0
42332 30447 0
21852 6617 1
20000 23382 0
32297 4803 1
14563 34582 0
7667 22386 0
26562 23139 0
25281 7017 1
24027 29563 0
21471 43979 0
6113 36704 0
10743 28455 0
20694 10227 0
16574 402...

output:

50748

result:

ok single line: '50748'

Test #31:

score: 0
Accepted
time: 146ms
memory: 22836kb

input:

249943
52338 1932288 0
500604 85230 1
421975 541172 0
1220260 1922275 0
782273 1935347 0
1100991 1806280 0
205837 836278 0
314341 849646 0
482026 1814471 0
1006377 1795879 0
457197 1895481 1
612248 1804355 0
831860 7724 1
1975517 1191035 0
1838023 357991 0
1884236 960643 0
1978434 1272346 1
830 1056...

output:

237745

result:

ok single line: '237745'

Test #32:

score: 0
Accepted
time: 68ms
memory: 18428kb

input:

249924
1692009 1277080 0
1701311 1473926 0
1530920 1558948 0
809839 1544501 0
490718 1778464 0
1596606 1610103 0
1048061 322345 0
1093714 303163 0
1230443 1349196 0
85588 499676 1
710370 217252 0
700457 890768 0
1040631 611336 0
1222799 946458 0
1910466 490490 1
1683127 754616 0
876618 906063 0
4071...

output:

249924

result:

ok single line: '249924'

Test #33:

score: 0
Accepted
time: 90ms
memory: 17608kb

input:

249932
1729117 1770539 1
824212 56933 0
1124972 42036 0
13242 1217548 1
423680 121484 1
904678 196033 0
1845017 1617274 0
791653 394425 0
1584751 1586123 0
834207 7501 1
943442 1585395 0
1616144 144360 1
38206 943159 0
1094152 2372 1
475006 1310991 0
1960291 1348769 0
596237 300239 0
822162 866311 0...

output:

248067

result:

ok single line: '248067'

Test #34:

score: 0
Accepted
time: 455ms
memory: 95624kb

input:

249937
81362 1733185 0
1882027 356824 0
1301758 1983247 0
260027 229804 0
1529823 19648 0
558704 63525 1
627065 43140 1
1566709 1998530 0
1251941 1981808 1
1576571 52684 0
378011 1849464 0
53814 1410946 1
1660021 1755217 0
506015 83019 1
1253852 18492 1
328345 85484 0
424148 96850 0
1977974 1339668 ...

output:

193252

result:

ok single line: '193252'

Test #35:

score: 0
Accepted
time: 495ms
memory: 95996kb

input:

249959
184837 244754 0
948395 1933588 0
41827 88177 0
98303 36005 0
1777482 1742549 0
79639 514417 1
147209 233680 0
1634876 1911722 0
75372 133634 0
133448 84504 0
1656795 1938366 0
771498 14745 1
1459618 1930072 1
1678679 1938641 0
1049900 709 1
202162 267646 0
1991953 1856494 0
261064 1761408 1
1...

output:

81371

result:

ok single line: '81371'

Test #36:

score: 0
Accepted
time: 69ms
memory: 17960kb

input:

249910
1603379 1433343 1
164471 1557523 0
1159628 900250 1
1027168 579138 1
1450567 1867094 0
848409 326306 0
307054 1306503 0
695746 157643 1
1346167 1190499 1
1448398 1652741 1
1807909 1359563 0
175434 87592 0
605107 1359561 1
596349 1324954 0
1264020 1661491 1
983071 372870 1
928003 1824439 1
194...

output:

240919

result:

ok single line: '240919'

Test #37:

score: 0
Accepted
time: 159ms
memory: 48148kb

input:

249955
1062923 1830852 1
50817 1529810 0
1276748 1635310 1
161346 294127 1
1067911 1389639 1
89037 577579 0
124090 88710 0
304488 1799140 0
743644 1566242 1
1787471 1881511 0
49861 1400602 0
1982200 156553 0
12904 1845415 0
645314 1677556 1
1363699 1975028 0
1774517 1705053 0
958034 598649 1
1255417...

output:

210379

result:

ok single line: '210379'

Test #38:

score: 0
Accepted
time: 359ms
memory: 94140kb

input:

249996
1670925 231087 0
39527 1983657 0
473410 5370 0
1925481 1720431 0
67352 1896317 0
1504388 1726733 1
267185 1289444 1
1817474 1175113 1
1995074 1664245 0
499013 1967847 0
1648928 1862986 0
1939804 1720616 0
433527 39214 0
1515418 1862505 0
1616861 500050 1
1697588 1794243 0
1208156 242958 1
175...

output:

164113

result:

ok single line: '164113'

Test #39:

score: 0
Accepted
time: 270ms
memory: 47996kb

input:

249952
250574 1778462 0
1826747 837308 1
522919 1819222 0
134196 798730 1
408911 1769945 0
282572 1963935 0
1573844 350523 1
997645 179579 1
545660 1737010 1
1701480 1441783 1
1161949 1833221 1
1551370 59494 0
1532094 214104 0
720104 1906634 0
1336979 258825 1
639637 1880604 0
1678518 3671 0
519444 ...

output:

128606

result:

ok single line: '128606'

Test #40:

score: 0
Accepted
time: 585ms
memory: 94756kb

input:

249962
1570928 1168014 0
1289527 1069368 0
1084465 298630 0
1823246 970084 0
1448051 568213 0
57429 1877382 0
1985663 589872 0
192591 1581816 0
635580 1618658 0
1965199 1744436 0
973848 587670 0
1832568 1364683 0
204794 1526274 0
853401 597947 0
1706385 1388135 0
1394442 748004 0
1927023 1659075 0
1...

output:

23708

result:

ok single line: '23708'

Test #41:

score: 0
Accepted
time: 530ms
memory: 94244kb

input:

249972
884131 132698 0
1506894 1562766 0
777005 1622992 0
1966190 177651 0
367381 942169 0
1988383 6143 0
463050 689081 0
1910856 1788980 0
1840351 978821 0
1209453 1761364 0
434967 1586987 0
1112918 778466 0
1973192 456641 0
1503248 796976 0
1069319 1159757 1
7181 902472 0
923876 1689308 0
1450177 ...

output:

59018

result:

ok single line: '59018'

Test #42:

score: 0
Accepted
time: 177ms
memory: 56628kb

input:

249980
815485 1472579 0
408992 119891 1
613227 536688 0
56071 1821567 1
1798757 1911045 0
477565 1074082 1
934601 373894 0
1789967 302191 0
204776 1469559 1
466130 801703 1
1528053 265224 0
386174 1941600 1
1470080 1248956 0
849523 1043944 0
21679 337669 0
1006660 1824440 0
63376 187202 0
1397095 44...

output:

157728

result:

ok single line: '157728'