Submission #574075

#	Time	Username	Problem	Language	Result	Execution time	Memory
574075		MohammadAghil	Pinball (JOI14_pinball)	C++14	100 / 100	252 ms	15996 KiB

pinball

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<ll, ll> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, mod2 = 1500450271, maxn = 1e5 + 5, lg = 19, inf = ll(1e18) + 5, p = 9973;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

struct SEG{
     ll seg[maxn<<2];
     SEG(){
          fill(seg, seg + (maxn<<2), inf);
     }
     void upd(int i, ll k, int x = 1, int lx = 0, int rx = maxn){
          if(lx + 1 == rx) {
               seg[x] = min(seg[x], k);
               return;
          } 
          int mid = (lx + rx)>>1;
          if(i < mid) upd(i, k, x<<1, lx, mid);
          else upd(i, k, x<<1|1, mid, rx);
          seg[x] = min(seg[x<<1], seg[x<<1|1]);
     }
     ll get(int l, int r, int x = 1, int lx = 0, int rx = maxn){
          if(l <= lx && r >= rx) return seg[x];
          if(l >= rx || r <= lx) return inf;
          int mid = (lx + rx)>>1;
          return min(get(l, r, x<<1, lx, mid), get(l, r, x<<1|1, mid, rx));
     }
} seg[3];

int a[maxn], b[maxn], c[maxn], d[maxn], tp[maxn];

int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int n, m; cin >> n >> m;
     vector<int> pos;
     rep(i,0,n){
          cin >> a[i] >> b[i] >> c[i] >> d[i];
          if(a[i] == 1) tp[i] += 2;
          if(b[i] == m) tp[i] += 1;
          pos.pb(c[i]);
     } sort(all(pos)), pos.erase(unique(all(pos)), end(pos));
     auto get = [&](int x){ return lower_bound(all(pos), x) - begin(pos); };
     // for(int c: pos) cout << c << ' '; cout << '\n'; 
     rep(i,0,n){
          ll res1 = inf, res2 = inf;
          int l = get(a[i]), r = get(b[i] + 1);
          if(tp[i]&2){
               seg[2].upd(get(c[i]), res1 = d[i]);
          }else{
               seg[2].upd(get(c[i]), res1 = seg[2].get(l, r) + d[i]);
          }
          if(tp[i]&1){
               seg[1].upd(get(c[i]), res2 = d[i]);
          }else{
               seg[1].upd(get(c[i]), res2 = seg[1].get(l, r) + d[i]);
          }
          seg[0].upd(get(c[i]), min({
               inf,
               res1 + res2 - d[i],
               seg[0].get(l, r) + d[i]
          }));
          // rep(i,0,sz(pos)) rep(j,0,3) cout << seg[j].get(i, i + 1) << " \n"[j == 2];
          // cout << "__\n";
     }
     ll ans = seg[0].get(0, sz(pos));
     cout << (ans == inf? -1: ans) << '\n';
     return 0; 
}

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