oj.uz

Submission #98412

# Submission time Handle Problem Language Result Execution time Memory
98412 2019-02-23T07:44:42 Z 314rate Lightning Rod (NOI18_lightningrod) C++14
7 / 100
 2000 ms 123372 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 123372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 320 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2017 ms 110152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 123372 KB Time limit exceeded
2 Halted 0 ms 0 KB -