oj.uz

Submission #855222

# Submission time Handle Problem Language Result Execution time Memory
855222 2023-09-30T21:10:59 Z AndiR Sails (IOI07_sails) C++11
60 / 100
 1000 ms 3048 KB 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("");
ofstream fout ("");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
using pll=pair<ll, ll>;

ll n, aib[Nmax];

void aib_add(int l, int r, int val){
    while (l<=n){
        aib[l]+=val;
        l+=l&-l;
    }
    r++;
    while (r<=n){
        aib[r]-=val;
        r+=r&-r;
    }
}
ll aib_val(int pos){
    ll s=0;
    while (pos>0){
        s+=aib[pos];
        pos-=pos&-pos;
    }
    return s;
}
int aib_bs2(int val, int h){
    int l=1, r=h, mij, v, sol;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v>=val){
            sol=mij;
            l=mij+1;
        }
        else r=mij-1;
    }
    return sol;
}
int aib_bs1(int val, int h){
    int l=1, r=h, mij, v, sol;
    while (l<=r){
        mij=(l+r)/2;
        v=aib_val(mij);
        if (v<=val){
            sol=mij;
            r=mij-1;
        }
        else l=mij+1;
    }
    return sol;
}

struct mat{
    int h, k;
}v[Nmax];

bool cmp(mat a, mat b){
    return a.h<b.h;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for (int i=0; i<n; i++)
        cin>>v[i].h>>v[i].k;
    sort(v, v+n, cmp);
    for (int i=0; i<n; i++){
        ll val=aib_val(v[i].h-v[i].k+1);
        int l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
        int st=v[i].k-(v[i].h-r+1);
        aib_add(r, v[i].h, 1);
        aib_add(l, l+st-1, 1);
    }
    ll sol=0;
    for (int i=1; i<=n; i++)
        sol+=aib_val(i)*(aib_val(i)-1)/2;
    cout<<sol;
    return 0;
}

Compilation message

sails.cpp: In function 'int aib_bs2(int, int)':
sails.cpp:58:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |     return sol;
      |            ^~~
sails.cpp: In function 'int aib_bs1(int, int)':
sails.cpp:71:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |     return sol;
      |            ^~~
sails.cpp: In function 'int main()':
sails.cpp:29:12: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |     while (l<=n){
      |            ^
sails.cpp:61:27: note: 'sol' was declared here
   61 |     int l=1, r=h, mij, v, sol;
      |                           ^~~
sails.cpp:93:60: warning: 'sol' may be used uninitialized in this function [-Wmaybe-uninitialized]
   93 |         int l=aib_bs1(val, v[i].h), r=aib_bs2(val, v[i].h)+1;
      |                                                            ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.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 #5
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 #6
0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1728 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3048 KB Output is correct
2 Correct 43 ms 2512 KB Output is correct