QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#683470 | #9519. Build a Computer | wt_vic | AC ✓ | 1ms | 6096kb | C++14 | 8.7kb | 2024-10-27 21:19:08 | 2024-10-27 21:19:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solveK() {
ll n,m;
cin >> n >> m;
vector<ll>w(n),l(n),r(n),p(n);
ll s = 0;
for(int i = 0;i < n;i ++ ) {
cin >> w[i] >> l[i] >> r[i];
s += l[i];
}
iota(p.begin(),p.end(),0);
sort(p.begin(),p.end(),[&](int a,int b) {
return w[a] > w[b];
});
vector<ll>rs(n + 1),ls(n + 1),d(n + 1);
for(int i = 0;i < n;i ++ ) {
int id = p[i];
ls[i + 1] = ls[i] + w[id] * l[id];
rs[i + 1] = rs[i] + w[id] * r[id];
d[i + 1] = d[i] + (r[id] - l[id]);
}
ll t = m - s,ans = 0;
for(int i = 1;i <= n;i ++ ) {
int id = p[i - 1];
t += l[id];
int pos = upper_bound(d.begin() + 1,d.end(),t) - d.begin() - 1;
ll res = 0;
if(pos < i) {
ll det = t - d[pos];// pos + 1 <= i - 1
res = rs[pos] + w[p[pos]] * det + (ls[n] - ls[i]) + (pos + 1 <= i - 1 ? (ls[i - 1] - ls[pos]) : 0);
}else {
ll det = t - d[i - 1];
res = rs[i - 1] + w[id] * det + (ls[n] - ls[i]);
}
ans = max(ans,res);
t -= l[id];
}
cout << ans << "\n";
}
const int N = 1e5 + 5;
struct Node
{
int l,r;
int x,len;
}tr[N << 2];
int a[N],b[N];
vector<int>p,d;
void pushup(int u) {
if(tr[u << 1].x == tr[u << 1].len)
tr[u].x = tr[u << 1].x + tr[u << 1 | 1].x;
else tr[u].x = tr[u << 1].x;
}
void build(int u,int l,int r) {
tr[u] = {l,r,0,r - l + 1};
if(l == r) {
if(a[p[l]] == 0)tr[u].x = 1;
else tr[u].x = 0;
return;
}
int mid = l + r >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
pushup(u);
}
void modify(int u,int x,int c) {
if(tr[u].l == tr[u].r) {
if(c == 0)tr[u].x = 1;
else tr[u].x = 0;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)modify(u << 1,x,c);
else modify(u << 1 | 1,x,c);
pushup(u);
}
int query(int u,int l,int r) {
if(tr[u].l >= l and tr[u].r <= r) {
if(tr[u].x == tr[u].len)return -1;
else return tr[u].x + tr[u].l;
}
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) {
int x = query(u << 1,l,r);
if(x != -1)return x;
}
if(r > mid) return query(u << 1 | 1,l,r);
assert(0);
return -1;
/*int x = query(u << 1,l,r);
if(x == -1) {
return query(u << 1 | 1,l,r);
}else return x;*/
}
void solveJ() {
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i ++ ) {
cin >> a[i];
b[i] = a[i];
}
int pre = 0;
d.clear(),p.clear();
p.push_back(0);
d.push_back(0);
vector<int>st(n + 1);
for(int i = 1;i <= m;i ++ ) {
int x,t;
cin >> x >> t;
int dis = x - pre;
pre = x;
p.push_back(t);
st[t] ++;
d.push_back(dis);
}
vector<int>nxt(m + 1,-1);
map<int,int>mp;
for(int i = m;i >= 1;i -- ) {
if(mp.count(p[i]))nxt[i] = mp[p[i]];
mp[p[i]] = i;
}
build(1,1,m);
ll sum = 0;
for(int i = 1;i <= n;i ++ ) {
if(!st[i])sum += a[i];
}
int k = 0;
ll ans = 0;
bool f = 0;
for(int i = 1;i <= m;i ++ ) {
int dis = d[i];
// if(i == 2)cerr << ans + sum << "\n";
while(dis > 0) {
int pos = query(1,i,m);
// cerr << pos << "\n";
// if(TestCase == 0)cerr << pos << "\n";
if(pos == -1) {
// cerr << sum << ' ' << dis << "\n";
if(sum >= dis) {
ans += dis;
sum -= dis;
dis = 0;
}else {
ans += sum;
dis -= sum;
sum = 0;
f = 1;break;
}
}else {
// cerr << a[p[pos]] << ' ' << dis << "\n";
if(dis >= a[p[pos]]) {
ans += a[p[pos]];
dis -= a[p[pos]];
modify(1,pos,0);
a[p[pos]] = 0;
}else {
ans += dis;
a[p[pos]] -= dis;
dis = 0;
}
}
}
if(f == 1)break;
if(nxt[i] != -1)modify(1,nxt[i],1),a[p[i]] = b[p[i]];
else sum += b[p[i]],a[p[i]] = 0,modify(1,i,0);
// cerr << sum << "\n";
}
ans += sum;
cout << ans << "\n";
}
typedef pair<int,int> pii;
vector<pii>G[101];
int link[101];
void solveA() {
int l,r;
cin >> l >> r;
memset(link,-1,sizeof link);
int node = 2,tar = 2;//起点为1 终点为2
int mx = 0;
function<void(int,int,int)> dfs = [&](int l,int r,int k) -> void {
int now = k;
int x = -1;
int t = 19;
if(l == r and (l == 0 || l == 1)) {
G[now].push_back({tar,l});
return;
}
while(!(r >> t & 1))t --;
if(l == r) {
for(int i = t;i;i -- ) {
G[now].push_back({++ node,(r >> i & 1)});
now = node;
}
G[now].push_back({tar,r & 1});
return;
}
for(int i = t;i >= 0;i -- ) {
if((r >> i & 1) != (l >> i & 1)) {
x = i;
break;
}else {
G[now].push_back({++ node,(r >> i & 1)});
now = node;
}
}
if(l == 0 and r == (1 << x + 1) - 1) {
// link 到 i -> i + 1 {0,1}的链
link[now] = x;
mx = max(mx,x);
return;
}
int s = l >> x << x;
if(x == 0) {
G[now].push_back({tar,1});
G[now].push_back({tar,0});
return;
}
// cout << l - s << ' ' << (1 << x) - 1 << endl;
// cout << 0 << ' ' << r - s - (1 << x) << endl;
G[now].push_back({node + 1,0});
G[now].push_back({node + 2,1});
int d = node;
node += 2;
dfs(l - s,(1 << x) - 1,d + 1);
int j = (__lg(r - s - (1 << x)));
j = max(j,0);
now = d + 2;
while(x != j + 1) {
G[now].push_back({++ node,0});
now = node;
j ++;
}
//if(d == 7)cout << d + 2 << now << "\n";
dfs(0,r - s - (1 << x),now);
};
int f1 = -1,f2 = -1;
for(int i = 0;i < 20;i ++ ) {
if(l >> i & 1)f1 = i;
if(r >> i & 1)f2 = i;
}
int L = l;
for(int i = f1 + 1;;i ++ ) {
int R = (1 << i) - 1;
R = min(R,r);
dfs(L,R,1);
if(R >= r) {
break;
}
L = R + 1;
}
if(mx != -1) {
G[node + 1].push_back({tar,1});
G[node + 1].push_back({tar,0});
for(int i = 2;i <= mx;i ++ ) {
G[node + i].push_back({node + i - 1,1});
G[node + i].push_back({node + i - 1,0});
}
for(int i = 1;i <= node;i ++ ) {
int x = link[i];
if(x == -1)continue;
// cout << i << ' ' << x << '\n';
if(x == 0) {
G[i].push_back({tar,1});
G[i].push_back({tar,0});
}
else {
G[i].push_back({node + x,1});
G[i].push_back({node + x,0});
}
}
}
cout << node + mx << "\n";
for(int i = 1;i <= node + mx;i ++ ) {
cout << G[i].size() << " ";
for(auto [v,w] : G[i]) {
cout << v << ' ' << w << ' ';
}
cout << "\n";
}
/*int c = 0;
for(int i = 1;i <= node + mx;i ++ ) {
for(auto [v,w] : G[i]) {
c ++;
cout << i << ' ' << v << ' ' << w << '\n';
}
}
cout << c << "\n";*/
}
set<int> g[101][101];
int dp[101],deg[101];
void bfs(int t) {
queue<int>q;
q.push(t);
while(!q.empty()) {
auto u = q.front();
q.pop();
for(int v = 1;v < 100;v ++ ) {
if(g[u][v].empty())continue;
// cout << u << ' ' << v << "\n";
dp[v] += g[u][v].size() * dp[u];
deg[v] -= g[u][v].size();
if(!deg[v])q.push(v);
}
}
}
void solve() {
int m;
cin >> m;
for(int i = 1;i <= m;i ++ ) {
int u,v,w;
cin >> u >> v >> w;
g[u][v].insert(w);
deg[v] ++;
}
dp[1] = 1;
bfs(1);
cout << dp[2];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
// cin >> T;
while(T -- ) {
solveA();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4120kb
input:
5 7
output:
5 1 3 1 0 2 4 0 5 1 1 2 1 2 2 1 2 0
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
10 27
output:
12 2 3 1 7 1 0 2 4 0 5 1 1 6 1 2 11 1 11 0 2 2 1 2 0 2 8 0 9 1 2 12 1 12 0 1 10 0 2 11 1 11 0 2 2 1 2 0 2 11 1 11 0
result:
ok ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 4272kb
input:
5 13
output:
10 2 3 1 6 1 0 2 4 0 5 1 1 2 1 2 2 1 2 0 2 7 0 8 1 2 10 1 10 0 1 9 0 2 2 1 2 0 2 2 1 2 0
result:
ok ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 5924kb
input:
1 1000000
output:
96 20 2 1 3 1 4 1 7 1 10 1 13 1 16 1 19 1 22 1 25 1 28 1 31 1 34 1 37 1 40 1 43 1 46 1 49 1 52 1 55 1 0 2 2 1 2 0 2 5 0 6 1 2 2 1 2 0 2 2 1 2 0 2 8 0 9 1 2 80 1 80 0 2 80 1 80 0 2 11 0 12 1 2 81 1 81 0 2 81 1 81 0 2 14 0 15 1 2 82 1 82 0 2 82 1 82 0 2 17 0 18 1 2 83 1 83 0 2 83 1 83...
result:
ok ok
Test #5:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
1 1
output:
2 1 2 1 0
result:
ok ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
7 9
output:
7 2 3 1 5 1 0 1 4 1 1 2 1 1 6 0 1 7 0 2 2 1 2 0
result:
ok ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
3 7
output:
6 2 3 1 4 1 0 1 2 1 2 5 0 6 1 2 2 1 2 0 2 2 1 2 0
result:
ok ok
Test #8:
score: 0
Accepted
time: 1ms
memory: 4012kb
input:
1 5
output:
5 3 2 1 3 1 4 1 0 2 2 1 2 0 1 5 0 2 2 1 2 0
result:
ok ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 4080kb
input:
1 4
output:
5 3 2 1 3 1 4 1 0 2 2 1 2 0 1 5 0 1 2 0
result:
ok ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 4088kb
input:
8 9
output:
5 1 3 1 0 1 4 0 1 5 0 2 2 1 2 0
result:
ok ok
Test #11:
score: 0
Accepted
time: 0ms
memory: 6036kb
input:
7 51
output:
18 4 3 1 5 1 8 1 11 1 0 1 4 1 1 2 1 2 6 0 7 1 2 16 1 16 0 2 16 1 16 0 2 9 0 10 1 2 17 1 17 0 2 17 1 17 0 2 12 0 13 1 2 18 1 18 0 1 14 0 1 15 0 2 16 1 16 0 2 2 1 2 0 2 16 1 16 0 2 17 1 17 0
result:
ok ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 4328kb
input:
51 79
output:
16 2 3 1 10 1 0 1 4 1 2 5 0 6 1 2 7 0 8 1 2 16 1 16 0 1 9 1 2 15 1 15 0 1 2 1 1 11 0 1 12 0 2 13 0 14 1 2 16 1 16 0 2 16 1 16 0 2 2 1 2 0 2 15 1 15 0
result:
ok ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
92 99
output:
14 1 3 1 0 2 4 0 5 1 1 6 1 1 11 0 1 7 1 1 8 1 2 9 0 10 1 2 2 1 2 0 2 2 1 2 0 1 12 0 1 13 0 2 14 1 14 0 2 2 1 2 0
result:
ok ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 5796kb
input:
27 36
output:
14 2 3 1 8 1 0 1 4 1 2 5 0 6 1 1 7 1 2 14 1 14 0 1 2 1 1 9 0 1 10 0 2 11 0 12 1 2 14 1 14 0 1 13 0 1 2 0 2 2 1 2 0
result:
ok ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
55 84
output:
19 2 3 1 9 1 0 1 4 1 2 5 0 6 1 1 7 1 2 18 1 18 0 1 8 1 1 2 1 1 10 0 2 11 0 12 1 2 19 1 19 0 1 13 0 2 14 0 15 1 2 17 1 17 0 1 16 0 1 2 0 2 2 1 2 0 2 17 1 17 0 2 18 1 18 0
result:
ok ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
297208 929600
output:
72 2 3 1 29 1 0 2 4 0 5 1 2 6 0 7 1 2 71 1 71 0 1 8 1 2 70 1 70 0 2 9 0 10 1 2 11 0 12 1 2 68 1 68 0 2 13 0 14 1 2 67 1 67 0 1 15 1 2 66 1 66 0 2 16 0 17 1 2 18 0 19 1 2 64 1 64 0 2 20 0 21 1 2 63 1 63 0 1 22 1 2 62 1 62 0 1 23 1 1 24 1 1 25 1 1 26 1 2 27 0 28 1 2 56 1 56 0...
result:
ok ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
45728 589156
output:
74 5 3 1 21 1 24 1 27 1 30 1 0 2 4 0 5 1 1 6 1 2 71 1 71 0 1 7 1 2 8 0 9 1 2 10 0 11 1 2 68 1 68 0 1 12 1 2 67 1 67 0 2 13 0 14 1 1 15 1 2 65 1 65 0 2 16 0 17 1 1 18 1 2 63 1 63 0 2 19 0 20 1 2 61 1 61 0 2 61 1 61 0 2 22 0 23 1 2 72 1 72 0 2 72 1 72 0 2 25 0 26 1 2 73 1 73 0 ...
result:
ok ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
129152 138000
output:
50 2 3 1 18 1 0 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 2 9 0 10 1 2 11 0 12 1 2 48 1 48 0 2 13 0 14 1 2 47 1 47 0 1 15 1 2 46 1 46 0 2 16 0 17 1 2 44 1 44 0 2 44 1 44 0 1 19 0 1 20 0 1 21 0 1 22 0 2 23 0 24 1 2 50 1 50 0 2 25 0 26 1 2 49 1 49 0 1 27 0 2 28 0 29 1 2 47 1 47 0 2 30 ...
result:
ok ok
Test #19:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
245280 654141
output:
71 3 3 1 22 1 25 1 0 1 4 1 1 5 1 2 6 0 7 1 1 8 1 2 68 1 68 0 1 9 1 1 10 1 1 11 1 1 12 1 2 13 0 14 1 2 15 0 16 1 2 62 1 62 0 2 17 0 18 1 2 61 1 61 0 1 19 1 2 60 1 60 0 2 20 0 21 1 2 58 1 58 0 2 58 1 58 0 2 23 0 24 1 2 71 1 71 0 2 71 1 71 0 1 26 0 1 27 0 2 28 0 29 1 2 70 1 7...
result:
ok ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 4080kb
input:
202985 296000
output:
63 2 3 1 29 1 0 1 4 1 2 5 0 6 1 2 7 0 8 1 2 63 1 63 0 2 9 0 10 1 2 62 1 62 0 1 11 1 2 61 1 61 0 1 12 1 2 13 0 14 1 2 15 0 16 1 2 58 1 58 0 2 17 0 18 1 2 57 1 57 0 1 19 1 2 56 1 56 0 1 20 1 1 21 1 2 22 0 23 1 1 24 1 2 52 1 52 0 2 25 0 26 1 2 27 0 28 1 2 50 1 50 0 1 2 1 2 2 ...
result:
ok ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
438671 951305
output:
69 2 3 1 29 1 0 1 4 1 2 5 0 6 1 1 7 1 2 67 1 67 0 2 8 0 9 1 1 10 1 2 65 1 65 0 1 11 1 2 12 0 13 1 2 14 0 15 1 2 62 1 62 0 2 16 0 17 1 2 61 1 61 0 1 18 1 2 60 1 60 0 1 19 1 2 20 0 21 1 2 22 0 23 1 2 57 1 57 0 2 24 0 25 1 2 56 1 56 0 1 26 1 2 55 1 55 0 1 27 1 1 28 1 1 2 1 2...
result:
ok ok
Test #22:
score: 0
Accepted
time: 1ms
memory: 4048kb
input:
425249 739633
output:
71 2 3 1 30 1 0 1 4 1 2 5 0 6 1 2 7 0 8 1 2 70 1 70 0 1 9 1 2 69 1 69 0 1 10 1 1 11 1 1 12 1 1 13 1 2 14 0 15 1 1 16 1 2 63 1 63 0 2 17 0 18 1 2 19 0 20 1 2 61 1 61 0 1 21 1 2 60 1 60 0 2 22 0 23 1 2 24 0 25 1 2 58 1 58 0 2 26 0 27 1 2 57 1 57 0 2 28 0 29 1 2 56 1 56 0 1 2...
result:
ok ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 6096kb
input:
551207 961718
output:
75 1 3 1 0 2 4 0 5 1 2 6 0 7 1 2 33 0 34 1 2 8 0 9 1 2 75 1 75 0 2 10 0 11 1 2 74 1 74 0 1 12 1 2 73 1 73 0 1 13 1 2 14 0 15 1 1 16 1 2 70 1 70 0 2 17 0 18 1 2 19 0 20 1 2 68 1 68 0 1 21 1 2 67 1 67 0 2 22 0 23 1 2 24 0 25 1 2 65 1 65 0 1 26 1 2 64 1 64 0 2 27 0 28 1 2 29 0...
result:
ok ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 4272kb
input:
114691 598186
output:
77 4 3 1 31 1 34 1 37 1 0 1 4 1 1 5 1 2 6 0 7 1 2 8 0 9 1 2 73 1 73 0 2 10 0 11 1 2 72 1 72 0 2 12 0 13 1 2 71 1 71 0 2 14 0 15 1 2 70 1 70 0 2 16 0 17 1 2 69 1 69 0 2 18 0 19 1 2 68 1 68 0 2 20 0 21 1 2 67 1 67 0 2 22 0 23 1 2 66 1 66 0 2 24 0 25 1 2 65 1 65 0 2 26 0 27 1 2 ...
result:
ok ok
Test #25:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
234654 253129
output:
57 1 3 1 0 1 4 1 1 5 1 2 6 0 7 1 2 8 0 9 1 1 27 0 1 10 1 2 57 1 57 0 2 11 0 12 1 1 13 1 2 55 1 55 0 2 14 0 15 1 2 16 0 17 1 2 53 1 53 0 1 18 1 2 52 1 52 0 2 19 0 20 1 2 21 0 22 1 2 50 1 50 0 1 23 1 2 49 1 49 0 1 24 1 1 25 1 1 26 1 2 2 1 2 0 2 28 0 29 1 2 56 1 56 0 2 30 0 ...
result:
ok ok
Test #26:
score: 0
Accepted
time: 0ms
memory: 4296kb
input:
554090 608599
output:
61 1 3 1 0 1 4 0 1 5 0 2 6 0 7 1 2 8 0 9 1 1 30 0 1 10 1 2 61 1 61 0 1 11 1 1 12 1 2 13 0 14 1 1 15 1 2 57 1 57 0 2 16 0 17 1 2 18 0 19 1 2 55 1 55 0 2 20 0 21 1 2 54 1 54 0 1 22 1 2 53 1 53 0 1 23 1 2 24 0 25 1 1 26 1 2 50 1 50 0 2 27 0 28 1 1 29 1 2 48 1 48 0 2 2 1 2 0 ...
result:
ok ok
Extra Test:
score: 0
Extra Test Passed