QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#683470#9519. Build a Computerwt_vicAC ✓1ms6096kbC++148.7kb2024-10-27 21:19:082024-10-27 21:19:10

Judging History

This is the latest submission verdict.

  • [2024-10-27 21:19:10]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 6096kb
  • [2024-10-27 21:19:08]
  • Submitted

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