oj.uz

Submission #971900

# Submission time Handle Problem Language Result Execution time Memory
971900 2024-04-29T12:54:46 Z yeediot Pinball (JOI14_pinball) C++17
100 / 100
 212 ms 30372 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
vector<int>temp;
int get(int x){
    return lower_bound(all(temp),x)-temp.begin()+1;
}
const int mxn=3e5+5;
const int inf=1e18;
int n;
struct segtree{
    int seg[4*mxn];
    bool upd=0;
    void build(int l,int r,int id){
        seg[id]=inf;
        if(l==r){
            return;
        }
        int mm=l+r>>1;
        build(l,mm,id*2);
        build(mm+1,r,id*2+1);
    }
    void modify(int l,int r,int id,int p,int v){
        if(l==r){
            if(v<=seg[id]){
                upd=1;
            }
            chmin(seg[id],v);
            return;
        }
        int mm=l+r>>1;
        if(p<=mm){
            modify(l,mm,id*2,p,v);
        }
        else{
            modify(mm+1,r,id*2+1,p,v);
        }
        seg[id]=min(seg[id*2],seg[id*2+1]);
    }
    int query(int l,int r,int id,int ql,int qr){
        if(qr<l or r<ql){
            return inf;
        }
        if(ql<=l and r<=qr){
            return seg[id];
        }
        int mm=l+r>>1;
        return min(query(l,mm,id*2,ql,qr),query(mm+1,r,id*2+1,ql,qr));
    }
    void modify(int p,int v){
        modify(1,sz(temp),1,get(p),min(v,inf));
    }
    int query(int ql,int qr){
        return query(1,sz(temp),1,get(ql),get(qr));
    }
}tl,tr;
vector<tuple<int,int,int,int>>v;
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        temp.pb(a);
        temp.pb(b);
        temp.pb(c);
        v.pb({a,b,c,d});
    }
    temp.pb(1);
    temp.pb(m);
    sort(all(temp));
    temp.resize(unique(all(temp))-temp.begin());
    tl.build(1,sz(temp),1);
    tr.build(1,sz(temp),1);
    tl.modify(1,0);
    tr.modify(m,0);
    int ans=inf;
    for(int i=1;i<=n;i++){
        auto [a,b,c,d]=v[i-1];
        bool mn=0;
        tl.upd=0;
        tr.upd=0;
        int x=tl.query(a,b);
        int y=tr.query(a,b);
        chmin(ans,x+y+d);
        tl.modify(c,x+d);
        tr.modify(c,y+d);
    }
    cout<<(ans>=1e18?-1:ans)<<'\n';
}
 /*
 input:
 
 */

Compilation message

pinball.cpp: In member function 'void segtree::build(long long int, long long int, long long int)':
pinball.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mm=l+r>>1;
      |                ~^~
pinball.cpp: In member function 'void segtree::modify(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:81:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |         int mm=l+r>>1;
      |                ~^~
pinball.cpp: In member function 'long long int segtree::query(long long int, long long int, long long int, long long int, long long int)':
pinball.cpp:97:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |         int mm=l+r>>1;
      |                ~^~
pinball.cpp: In function 'int main()':
pinball.cpp:133:14: warning: unused variable 'mn' [-Wunused-variable]
  133 |         bool mn=0;
      |              ^~
pinball.cpp: In function 'void setIO(std::string)':
pinball.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pinball.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2524 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2524 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 2 ms 2532 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2524 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 2 ms 2652 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 2 ms 2532 KB Output is correct
20 Correct 2 ms 2652 KB Output is correct
21 Correct 1 ms 2396 KB Output is correct
22 Correct 2 ms 2652 KB Output is correct
23 Correct 2 ms 2652 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 18 ms 5588 KB Output is correct
26 Correct 40 ms 7112 KB Output is correct
27 Correct 119 ms 13376 KB Output is correct
28 Correct 108 ms 14516 KB Output is correct
29 Correct 85 ms 11660 KB Output is correct
30 Correct 146 ms 15776 KB Output is correct
31 Correct 185 ms 22184 KB Output is correct
32 Correct 172 ms 17820 KB Output is correct
33 Correct 22 ms 6604 KB Output is correct
34 Correct 90 ms 15892 KB Output is correct
35 Correct 118 ms 29600 KB Output is correct
36 Correct 212 ms 29736 KB Output is correct
37 Correct 180 ms 30372 KB Output is correct
38 Correct 165 ms 28584 KB Output is correct