oj.uz

Submission #575462

# Submission time Handle Problem Language Result Execution time Memory
575462 2022-06-10T15:47:15 Z keta_tsimakuridze Sails (IOI07_sails) C++17
100 / 100
 118 ms 2288 KB 
 #include<bits/stdc++.h>
 #define ll long long
 #define f first
 #define s second
 using namespace std;
 const int N = 2e5 + 5;
 int n, c[N], tree[N], H;
 void upd(int id, int t) {
    for(id; id <= H; id += id & (-id)) tree[id] += t;
 }
 int get(int id) {
    int ans  =0;
    for(id; id >= 1; id -= id & (-id)) ans += tree[id];
    return ans;
 }
 int main() {
    cin >> n;
    vector<pair<int,int> > v;
    for(int i = 1; i <= n; i++) {
        int h, k; cin >> h >> k;
        v.push_back({h, k});
        H = max(H, h);
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++) {
        int k = v[i].s, h = v[i].f;
        // h - k + 1
        int cn = get(h - k + 1);
        int l = 1, r = h - k + 1, L = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(get(mid) == cn) L = mid, r = mid - 1;
            else l = mid + 1;
        }
        l = h - k + 1, r = h;
        int  R = 0;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(get(mid) == cn) R = mid, l = mid + 1;
            else r = mid - 1;
        }
       // cout << "++" << get(3) << "  "  << get(2) << endl;
        //cout << k << " " << h << " " << R + 1 << " " << h << endl;
        upd(R + 1, 1); upd(h + 1, -1);
        k -= h - R;
       // cout << L  << " " << L + k << endl;
        upd(L, 1); upd(L + k, -1);
    }
    ll ans = 0;
    for(int i = 1; i <= H; i++) {
        int cn = get(i);
        ans += (ll)cn * (cn - 1)/ 2;
    }
    cout << ans;

 }

Compilation message

sails.cpp: In function 'void upd(int, int)':
sails.cpp:9:9: warning: statement has no effect [-Wunused-value]
    9 |     for(id; id <= H; id += id & (-id)) tree[id] += t;
      |         ^~
sails.cpp: In function 'int get(int)':
sails.cpp:13:9: warning: statement has no effect [-Wunused-value]
   13 |     for(id; id >= 1; id -= id & (-id)) ans += tree[id];
      |         ^~
sails.cpp: In function 'int main()':
sails.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < v.size(); i++) {
      |                    ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 468 KB Output is correct
2 Correct 29 ms 960 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 720 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 1184 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1400 KB Output is correct
2 Correct 99 ms 2288 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1512 KB Output is correct
2 Correct 74 ms 2080 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1480 KB Output is correct
2 Correct 81 ms 2284 KB Output is correct