Submission #758861

#	Time	Username	Problem	Language	Result	Execution time	Memory
758861		keta_tsimakuridze	허수아비 (JOI14_scarecrows)	C++14	100 / 100	1039 ms	35144 KiB

scarecrows

#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(){
    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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85