oj.uz

Submission #921544

# Submission time Handle Problem Language Result Execution time Memory
921544 2024-02-04T06:16:08 Z vjudge1 Lightning Rod (NOI18_lightningrod) C++17
40 / 100
 2000 ms 158428 KB 
#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);
    for(int i=n;i>=2;i--){
        if(u[i]==1){
            continue;
        }
        for(int j=i-1;j>=1;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 2029 ms 152192 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 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 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 2 ms 348 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 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 2 ms 348 KB Output is correct
14 Correct 218 ms 4772 KB Output is correct
15 Correct 153 ms 4996 KB Output is correct
16 Execution timed out 2065 ms 4692 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 2044 ms 158428 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 2029 ms 152192 KB Time limit exceeded
2 Halted 0 ms 0 KB -