oj.uz

Submission #758864

# Submission time Handle Problem Language Result Execution time Memory
758864 2023-06-15T11:46:38 Z lukameladze 허수아비 (JOI14_scarecrows) C++17
100 / 100
 1104 ms 34752 KB 
# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
// #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n;
long long ans;
pii a[N];
map <int, int> mp;
void g(vector <int> v) {
    sort(v.begin(),v.end());
    int cnt = 0;
    for (int i = 0 ; i < v.size(); i++) {
        if (i == 0 || v[i] != v[i - 1]) cnt++, mp[v[i]] = cnt;
    }
}
void comp() {
    vector <int> v;
    for (int i = 1; i <= n; i++) {
        v.pb(a[i].f);
    }
    g(v);
    for (int i = 1; i <= n; i++) {
        a[i].f = mp[a[i].f];
    }
    v.clear();
    for (int i = 1; i <= n; i++) {
        v.pb(a[i].s);
    }
    g(v);
    for (int i = 1; i <= n; i++) {
        a[i].s = mp[a[i].s];
    }
    sort(a + 1, a + n + 1);
}
int tree[N];
void upd(int idx, int val){
    assert(idx != 0);
    for (int i = idx; i < N; i+=i&(-i)) {
        tree[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree[i];
    }
    return pas;
}
void solve(int le, int ri) {
    if (le == ri) return ;
    int mid = (le + ri) / 2;
    set <int> s;
    s.insert(0);
    vector <pii> vecle, vecri;
    for (int i = mid + 1; i <= ri; i++) {
        // patarebshi maximaluri
        auto it = --s.lower_bound(a[i].s);
        int x = (*it);
        if (x + 1 <= a[i].s)
        vecri.pb({x + 1, a[i].s});
        s.insert(a[i].s);
    }
    s.clear();
    s.insert(n + 5);
    for (int i = mid; i >= le; i--) {
        auto it = s.upper_bound(a[i].s);
        int x = (*it);
        if (a[i].s <= (x - 1))
        vecle.pb({a[i].s, x - 1});
        s.insert(a[i].s);
    }
    // ro ikvetebian masetebis raodenoba
    sort(vecle.begin(), vecle.end());
    sort(vecri.begin(), vecri.end());
    /*for (pii sth : vecle) {
        cout<<sth.f<<" "<<sth.s<<"\n";
    }
    for (pii sth : vecri) {
        cout<<sth.f<<"-"<<sth.s<<"\n";
    }
    cout<<"\n";*/
    int id = 0;
    for (pii sth : vecle) {
        while (id < vecri.size() && vecri[id].f <= sth.f) {
            upd(vecri[id].s, 1);
            id++;
        }
        ans += (getans(sth.s) - getans(sth.f - 1));
    }

    for (int i = 0; i < id; i++) {
        upd(vecri[i].s, -1);
    }
    solve(le, mid);
    solve(mid + 1, ri);
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for (int i = 1; i <= n; i++) {
        cin>>a[i].f>>a[i].s;
	}
    comp();
    solve(1, n);
    cout<<ans<<"\n";
}

Compilation message

scarecrows.cpp: In function 'void g(std::vector<int>)':
scarecrows.cpp:16:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0 ; i < v.size(); i++) {
      |                      ~~^~~~~~~~~~
scarecrows.cpp: In function 'void solve(int, int)':
scarecrows.cpp:88:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         while (id < vecri.size() && vecri[id].f <= sth.f) {
      |                ~~~^~~~~~~~~~~~~~
scarecrows.cpp: At global scope:
scarecrows.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1008 KB Output is correct
2 Correct 15 ms 1236 KB Output is correct
3 Correct 15 ms 1240 KB Output is correct
4 Correct 12 ms 996 KB Output is correct
5 Correct 14 ms 1108 KB Output is correct
6 Correct 15 ms 1224 KB Output is correct
7 Correct 15 ms 1236 KB Output is correct
8 Correct 11 ms 1240 KB Output is correct
9 Correct 14 ms 1244 KB Output is correct
10 Correct 15 ms 1156 KB Output is correct
11 Correct 15 ms 1168 KB Output is correct
12 Correct 11 ms 1048 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 684 ms 25264 KB Output is correct
2 Correct 1065 ms 34360 KB Output is correct
3 Correct 910 ms 34724 KB Output is correct
4 Correct 621 ms 25260 KB Output is correct
5 Correct 885 ms 32312 KB Output is correct
6 Correct 999 ms 33888 KB Output is correct
7 Correct 1061 ms 34256 KB Output is correct
8 Correct 1104 ms 34356 KB Output is correct
9 Correct 737 ms 34696 KB Output is correct
10 Correct 927 ms 34752 KB Output is correct
11 Correct 1000 ms 34528 KB Output is correct
12 Correct 1042 ms 34452 KB Output is correct
13 Correct 1070 ms 34404 KB Output is correct
14 Correct 745 ms 34712 KB Output is correct
15 Correct 1004 ms 34456 KB Output is correct
16 Correct 1059 ms 34356 KB Output is correct
17 Correct 603 ms 22380 KB Output is correct
18 Correct 1006 ms 34500 KB Output is correct
19 Correct 1000 ms 34588 KB Output is correct
20 Correct 995 ms 34668 KB Output is correct