Submission #98412

#	Time	Username	Problem	Language	Result	Execution time	Memory
98412		314rate	Lightning Rod (NOI18_lightningrod)	C++14	7 / 100	2036 ms	123372 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Point
{
        int x;
        int y;
        int inA;
};

bool cmp1(Point v, Point b)
{
        return v.y > b.y;
}

bool cmp2(Point v, Point b)
{
        return v.x < b.x;
}

const int N = (int)1e7 + 7;

int n;
Point a[N];
Point v[N];
bool viz[N];

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        cin >> n;
        for(int i = 1; i <= n; i++)
        {
                cin >> v[i].x >> v[i].y;
        }
        sort(v + 1, v + n + 1, cmp1);
        for(int i = 1; i <= n; i++)
        {
                v[i].inA = i;
                a[i] = v[i];
        }
        sort(v + 1, v + n + 1, cmp2);
        int r = 0;
        for(int it = 1; it <= n; it++)
        {
                int i = v[it].inA;
                if(viz[i] == 0)
                {
                        r++;
                        for(int j = i; j >= 1; j--)
                        {
                                if(viz[j]) break;
                                int dif = abs(v[i].x - v[j].x);
                                if(dif > v[i].y - v[j].y)
                                {
                                        break;
                                }
                                viz[j] = 1;
                        }
                        for(int j = i + 1; j <= n; j++)
                        {
                                if(viz[j]) break;
                                int dif = abs(v[i].x - v[j].x);
                                if(dif > v[i].y - v[j].y)
                                {
                                        break;
                                }
                                viz[j] = 1;
                        }
                }
        }
        cout << r << "\n";
        return 0;
}
/**

**/

• Subtask 1: 0 / 4
• Subtask 2: 7 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 21
• Subtask 5: 0 / 26
• Subtask 6: 0 / 10
• Subtask 7: 0 / 20