Submission #921541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921541	2024-02-04T06:13:46 Z	vjudge1	Lightning Rod (NOI18_lightningrod)	C++17	40 / 100	2000 ms	208688 KB

lightningrod

#include <bits/stdc++.h>
#include <iomanip>
#define ll long long
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define str string
#define pii pair<int,int>
#define sz(x) x.size()
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define mii map<int,int>
#define mll map<ll,ll>
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yess cout<<"Yes\n";
#define noo cout<<"No\n";
using namespace std;

#define maxn 1111111
#define mod  1000000007

int u[10000001];

void solve(){
    int n;
    cin>>n;
    pair<int,int>a[n+3];
    for(int i=1;i<=n;i++){
        cin>>a[i].ss>>a[i].ff;
    }
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(u[i]==1){
            continue;
        }
        for(int j=i+1;j<=n;j++){
            //cout<<(abs(a[i].ss-a[j].ss)<=a[i].ff-a[j].ff)<<" "<<a[i].ss<<" "<<a[j].ss<<" "<<a[i].ff<<" "<<a[j].ff<<"\n";
            if(abs(a[i].ss-a[j].ss)<=a[i].ff-a[j].ff){
                u[j]=1;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=(u[i]==0);
    }
    cout<<ans;
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	//srand( time(0));
	//freopen("sum.in", "r", stdin);
	//freopen("sum.out", "w", stdout);
    int tests=1;
    //cin>>tests;
    for(int i=1;i<=tests;i++){
		//cout<<"Case "<<i<<": \n";
		solve();
	}
}

Subtask #1

0 / 4.0

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

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	464 KB	Output is correct

Subtask #3

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	464 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	464 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct

Subtask #4

21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	464 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	464 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	344 KB	Output is correct

Subtask #5

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	464 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	464 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	3 ms	344 KB	Output is correct
14	Correct	222 ms	7608 KB	Output is correct
15	Correct	169 ms	7760 KB	Output is correct
16	Execution timed out	2063 ms	6868 KB	Time limit exceeded
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2037 ms	206804 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	2089 ms	208688 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-