oj.uz

Submission #758862

# Submission time Handle Problem Language Result Execution time Memory
758862 2023-06-15T11:38:15 Z keta_tsimakuridze 허수아비 (JOI14_scarecrows) C++14
100 / 100
 1000 ms 31304 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 4e5 + 5, mod = 1e9 + 7; // !
int D[N], U[N], t[N];
pair<int,int> e[N];
int ans = 0;
vector<int> x;
void upd(int id, int v) {
    id = max(id, 1ll);
    for(id; id <= (int)x.size(); id += id & (-id)) t[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += t[id];
    return ans;
}
//vector<pair<int,int>> x;
void solve(int l, int r) {
    if(l == r) return;
    int mid = (l + r) / 2;
    vector<pair<int,int>> X, Y;
    set<int> s; s.insert(0);
    for(int i = mid + 1; i <= r; i++) {
        D[i] = *--s.upper_bound(e[i].s);
        X.push_back({e[i].s, D[i]}); // e[i].s ---- D[i] chatvlit ramdeni iseti tipiiiaaaa rom U[j] >= e[i].s DAAA e[j].s <= e[i].s && e[j].s >= D[u]
        s.insert(e[i].s);
        // sadamde awyobs chasvla
    }
    s.clear(); s.insert((int)x.size() + 1);
    for(int i = mid; i >= l; i--) {
        U[i] = *s.upper_bound(e[i].s);
        s.insert(e[i].s);
        Y.push_back({U[i], e[i].s});
    }
    sort(X.rbegin(), X.rend());
    sort(Y.begin(), Y.end());
    vector<int> roll;
    for(int i = 0; i < (int)X.size(); i++) {
        while(Y.size() && Y.back().f >= X[i].f) {
            roll.push_back(Y.back().s);
            upd(Y.back().s, 1);
            Y.pop_back();
        }
        ans += get(X[i].f) - get(X[i].s - 1);
    }
    while(roll.size()) upd(roll.back(), -1), roll.pop_back();
//    cout << ans;
//    exit(0);
    solve(l, mid); solve(mid + 1, r);
}
int GET(int b) {
    return (lower_bound(x.begin(), x.end(), b) - x.begin()) + 1;
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> e[i].f >> e[i].s;
        x.push_back(e[i].f);
        x.push_back(e[i].s);
    }
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    for(int i = 1; i <= n; i++) {
        e[i].f = GET(e[i].f);
        e[i].s = GET(e[i].s);
    }

    sort(e + 1, e + n + 1);

    solve(1, n);
    cout << ans;
 }

Compilation message

scarecrows.cpp: In function 'void upd(long long int, long long int)':
scarecrows.cpp:14:9: warning: statement has no effect [-Wunused-value]
   14 |     for(id; id <= (int)x.size(); id += id & (-id)) t[id] += v;
      |         ^~
scarecrows.cpp: In function 'long long int get(long long int)':
scarecrows.cpp:18:9: warning: statement has no effect [-Wunused-value]
   18 |     for(id; id >= 1; id -= id & (-id)) ans += t[id];
      |         ^~
scarecrows.cpp: At global scope:
scarecrows.cpp:58:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   58 | 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 2 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 10 ms 1108 KB Output is correct
2 Correct 15 ms 1140 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Correct 9 ms 1000 KB Output is correct
5 Correct 14 ms 1124 KB Output is correct
6 Correct 16 ms 1132 KB Output is correct
7 Correct 18 ms 1160 KB Output is correct
8 Correct 10 ms 1108 KB Output is correct
9 Correct 14 ms 1108 KB Output is correct
10 Correct 15 ms 1156 KB Output is correct
11 Correct 14 ms 1108 KB Output is correct
12 Correct 10 ms 976 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 29824 KB Output is correct
2 Correct 974 ms 31108 KB Output is correct
3 Correct 764 ms 31000 KB Output is correct
4 Correct 541 ms 27888 KB Output is correct
5 Correct 823 ms 30812 KB Output is correct
6 Correct 886 ms 31032 KB Output is correct
7 Correct 931 ms 31028 KB Output is correct
8 Correct 972 ms 31120 KB Output is correct
9 Correct 650 ms 31292 KB Output is correct
10 Correct 822 ms 31180 KB Output is correct
11 Correct 884 ms 30900 KB Output is correct
12 Correct 931 ms 31260 KB Output is correct
13 Correct 1000 ms 31296 KB Output is correct
14 Correct 667 ms 31200 KB Output is correct
15 Correct 893 ms 31132 KB Output is correct
16 Correct 987 ms 31304 KB Output is correct
17 Correct 545 ms 19784 KB Output is correct
18 Correct 948 ms 30360 KB Output is correct
19 Correct 919 ms 29912 KB Output is correct
20 Correct 916 ms 29952 KB Output is correct