oj.uz

답안 #446067

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446067 2021-07-20T16:44:59 Z simon2712 별들과 삼각형 (IZhO11_triangle) C++14
0 / 100
 1 ms 204 KB 
#include <bits/stdc++.h>
using namespace std;
ifstream fin("triangles.in");
ofstream fout("triangles.out");
pair<int,int> v[3000001],v2[3000001];
int main()
{
    int n,i,st,dr,mij,st2,dr2,st3,dr3;
    unsigned long long rez=0;
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i].first>>v[i].second;
        v2[i].first=v[i].second;
        v2[i].second=v[i].first;
    }
    sort(v+1,v+n+1);
    sort(v2+1,v2+n+1);
    for(i=1;i<=n;i++)
    {
        st=1;
        dr=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij].first<=v[i].first)
                st=mij+1;
            else
                dr=mij-1;
        }
        st2=st-1;
        st=1;
        dr=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij].first>v[i].first)
                dr=mij-1;
            else
                st=mij+1;
        }
        dr2=dr;
        st=1;
        dr=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v2[mij].first<=v[i].second)
                st=mij+1;
            else
                dr=mij-1;
        }
        st3=st-1;
        st=1;
        dr=n;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v2[mij].first>v[i].second)
                dr=mij-1;
            else
                st=mij+1;
        }
        dr3=dr;
        rez+=(dr3-st3)*(dr2-st2);
    }
    fout<<rez;
    return 0;
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -