oj.uz

Submission #1076740

# Submission time Handle Problem Language Result Execution time Memory
1076740 2024-08-26T16:04:47 Z Faisal_Saqib Pairs (IOI07_pairs) C++17
30 / 100
 110 ms 6296 KB 
#pragma optimze("Ofast")
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;
// #define endl '\n'
#define ll long long
const int N=76;
int pre[N][N][N];
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
bitset<100> have1;
int have3[N][N][N];
void solve_1d()
{
    int n,d,m;
    cin>>n>>d>>m;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    long long cnt=0;
    sort(begin(a),end(a));
    int i=0;
    for(int j=0;j<n;j++)
    {
        while(i<n and a[i]<(a[j]-d))
        {
            i++;
        }
        cnt+=(j-i);
    }
    cout<<cnt<<'\n';
}
void solve_2d()
{
    int n,d,m;
    cin>>n>>d>>m;
    vector<pair<int,int>> b;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        b.push_back({x+y,x-y});
    }
    ordered_set sp;
    ll cnt=0;
    sort(begin(b),end(b));
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j<=i and (b[i].first-b[j].first)>d)
        {
            sp.erase(sp.upper_bound(b[j].second));
            j++;
        }
        int l=b[i].second-d;
        int r=b[i].second+d;
        cnt+=sp.order_of_key(r+1);
        cnt-=sp.order_of_key(l);
        sp.insert(b[i].second);
    }
    cout<<cnt<<'\n';
}
int main()
{
      ios::sync_with_stdio(false);
      cout.tie(NULL);
      cin.tie(NULL);
    int b,m;
    cin>>b;
    solve_2d();
}

Compilation message

pairs.cpp:1: warning: ignoring '#pragma optimze ' [-Wunknown-pragmas]
    1 | #pragma optimze("Ofast")
      | 
pairs.cpp: In function 'int main()':
pairs.cpp:77:11: warning: unused variable 'm' [-Wunused-variable]
   77 |     int b,m;
      |           ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 3896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 4304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2012 KB Output is correct
2 Correct 49 ms 6296 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2012 KB Output is correct
2 Correct 89 ms 4520 KB Output is correct
3 Correct 74 ms 4052 KB Output is correct
4 Correct 82 ms 3792 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2420 KB Output is correct
2 Correct 110 ms 4764 KB Output is correct
3 Correct 67 ms 5840 KB Output is correct
4 Correct 63 ms 4260 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 2456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 2512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -