제출 #406382

#제출 시각아이디문제언어결과실행 시간메모리
406382pure_mem팀들 (IOI15_teams)C++14
77 / 100
1515 ms368532 KiB
#include "teams.h" #include <bits/stdc++.h> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int MAXN = 5e5 + 12, BS = 300; struct node{ int val = 0; node *l = nullptr, *r = nullptr; node(int _val = 0, node* _l = nullptr, node* _r = nullptr){ val = _val, l = _l, r = _r; } }; int getVal(node* v){ return v ? v->val: 0; } node* upd(node* v, int tl, int tr, int pos, int val){ if(tl == tr) return new node(getVal(v) + val); int tm = (tl + tr) / 2; if(pos <= tm) v = new node(0, upd(v ? v->l: v, tl, tm, pos, val), v ? v->r: v); else v = new node(0, v ? v->l: v, upd(v ? v->r: v, tm + 1, tr, pos, val)); v->val = getVal(v->l) + getVal(v->r); return v; } int get(node* v, int tl, int tr, int l, int r){ if(tl > r || l > tr) return 0; if(tl >= l && tr <= r) return getVal(v); int tm = (tl + tr) / 2; return (v->l ? get(v->l, tl, tm, l, r): 0) + (v->r ? get(v->r, tm + 1, tr, l, r): 0); } node* root[MAXN]; int n, dp[MAXN]; vector< int > rv[MAXN], mine[MAXN]; void init(int N, int A[], int B[]) { n = N, root[0] = new node(); for(int i = 0;i < n;i++) rv[n - B[i] + 1].push_back(A[i]), mine[A[i]].push_back(B[i]); for(int i = 1;i <= n;i++){ root[i] = root[i - 1]; for(int v: rv[i]){ root[i] = upd(root[i], 1, n, v, 1); } } } int cf(int l, int r){ return get(root[n - r + 1], 1, n, l, r); } int can(int M, int K[]) { sort(K, K + M); vector< int > opt; int ptr = -1; for(int i = 0;i < M;i++){ dp[i] = cf(1, K[i]) - K[i]; while(ptr >= 1 && dp[opt[ptr - 1]] + cf(K[opt[ptr - 1]] + 1, K[i]) < dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i])) opt.pop_back(), ptr--; if(ptr >= 0) dp[i] = min(dp[i], dp[opt[ptr]] + cf(K[opt[ptr]] + 1, K[i]) - K[i]); ptr++, opt.push_back(i); if(dp[i] < 0) return 0; } return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...