Submission #968025

#	Time	Username	Problem	Language	Result	Execution time	Memory
968025		tset	Star triangles (IZhO11_triangle)	C++14	100 / 100	223 ms	21408 KiB

triangle

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define pii pair<int, int>

int firstEqual(vector<int>& v, int nb)
{
    int pos = -1;
    int pas = 1 << 20; 
    while(pas>0)
    {
        int test = pos + pas;
        if(test < v.size())
        {
            if(v[test] < nb)
            {
                pos += pas;
            }
        }
        pas /= 2;
    }
    return pos +1;
}

int nbAxis(vector<int>& v, int nb)
{
    return firstEqual(v, nb+1) - firstEqual(v, nb);
}

signed main()
{
    int N;
    scanf("%lld", &N);
    vector<int > X, Y;
    vector<pii> coords;
    for(int iN = 0; iN < N; iN++)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        X.push_back(x);
        Y.push_back(y);
        coords.push_back({x, y});
    }

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    int ans= 0;
    for(pii coord : coords)
    {
        int x = coord.first;
        int y = coord.second;
        int cx = nbAxis(X, x) -1;
        int cy = nbAxis(Y, y) -1;
        ans += cx * cy;
    }
    printf("%lld\n", ans);
}

Compilation message (stderr)

triangle.cpp: In function 'long long int firstEqual(std::vector<long long int>&, long long int)':
triangle.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         if(test < v.size())
      |            ~~~~~^~~~~~~~~~
triangle.cpp: In function 'int main()':
triangle.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%lld", &N);
      |     ~~~~~^~~~~~~~~~~~
triangle.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%lld%lld", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100