Submission #723800

#	Time	Username	Problem	Language	Result	Execution time	Memory
723800		kkts	Pinball (JOI14_pinball)	C++17	100 / 100	239 ms	14520 KiB

pinball

#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 = 3e5 + 5, mod = 1e9 + 7; // !
int tl[N], tr[N], M;
int getl(int id) {
    int mn = 1e18;
    for(id; id <= M; id += id & (-id)) mn = min(mn, tl[id]);
    return mn;
}
int getr(int id) {
    int mn = 1e18;
    for(id; id >= 1; id -= id & (-id)) mn = min(mn, tr[id]);
    return mn;
}
void updl(int id, int val) {
    for(id; id >= 1; id -= id & (-id)) tl[id]= min(tl[id], val);
}
void updr(int id, int val) {
    for(id; id <= M; id += id & (-id)) tr[id] = min(tr[id], val);
}
main(){
    int m, n;
    cin >> m >> n;
    vector<int> a(m + 2), b(m + 2), c(m + 2), d(m + 2);
    vector<int> x;
    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        x.push_back(a[i]);
        x.push_back(b[i]);
        x.push_back(c[i]);
    }
    x.push_back(1);
    x.push_back(n);
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    M = x.size();
    for(int i = 1; i <= M; i++) tl[i] = tr[i] = 1e18;
    int ans = 1e18;
    updl(1, 0);
    updr(x.size(), 0);
    for(int i = 1; i <= m; i++) {
        a[i] = lower_bound(x.begin(), x.end(), a[i]) - x.begin() + 1;
        b[i] = lower_bound(x.begin(), x.end(), b[i]) - x.begin() + 1;
        c[i] = lower_bound(x.begin(), x.end(), c[i]) - x.begin() + 1;

        int L = getl(a[i]), R = getr(b[i]);
        ans = min(ans, L + R + d[i]);
        updl(c[i], L + d[i]);
        updr(c[i], R + d[i]);
    }
    cout << (ans == 1e18 ? -1 : ans);
 }

Compilation message (stderr)

pinball.cpp: In function 'long long int getl(long long int)':
pinball.cpp:11:9: warning: statement has no effect [-Wunused-value]
   11 |     for(id; id <= M; id += id & (-id)) mn = min(mn, tl[id]);
      |         ^~
pinball.cpp: In function 'long long int getr(long long int)':
pinball.cpp:16:9: warning: statement has no effect [-Wunused-value]
   16 |     for(id; id >= 1; id -= id & (-id)) mn = min(mn, tr[id]);
      |         ^~
pinball.cpp: In function 'void updl(long long int, long long int)':
pinball.cpp:20:9: warning: statement has no effect [-Wunused-value]
   20 |     for(id; id >= 1; id -= id & (-id)) tl[id]= min(tl[id], val);
      |         ^~
pinball.cpp: In function 'void updr(long long int, long long int)':
pinball.cpp:23:9: warning: statement has no effect [-Wunused-value]
   23 |     for(id; id <= M; id += id & (-id)) tr[id] = min(tr[id], val);
      |         ^~
pinball.cpp: At global scope:
pinball.cpp:25:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   25 | main(){
      | ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49