Submission #8379003

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define N 4005
#define X 2001
#define M 200000


struct node {
    node *L,*R;
    int l,r, val[2];
};
node nodePool[M];
node *newNode() {
    static int pos = 0;
    nodePool[pos].L = nodePool[pos].R = NULL;
    nodePool[pos].val[0] = nodePool[pos].val[1] = 0;
    return &nodePool[pos++];
}
void init(node *root,int l,int r) {
    root->l = l;
    root->r = r;
    if(l==r) {
        return;
    }
    int mid = (l+r)/2;
    node *ln = newNode();
    init(ln,l,mid);
    node *rn = newNode();
    init(rn,mid+1,r);
    root->L = ln;root->R = rn;
}
void update(node *prev,node *cur,int l,int r,int ind,int bit) {
    cur->l = l;
    cur->r = r;
    if(l==r) {
        cur->val[0] = prev->val[0];
        cur->val[1] = prev->val[1];
        ++cur->val[bit];
        return;
    }
    int mid = (l+r)/2;
    if(ind<=mid) {
        cur->R = prev->R;
        node *ln = newNode();
        update(prev->L,ln,l,mid,ind,bit);
        cur->L = ln;
    } else {
        cur->L = prev->L;
        node *rn = newNode();
        update(prev->R,rn,mid+1,r,ind,bit);
        cur->R = rn;
    }
    cur->val[0] = cur->L->val[0] + cur->R->val[0];
    cur->val[1] = cur->L->val[1] + cur->R->val[1];
}
int query(node *root,int l,int r,int ql,int qr,int bit) {
    if(r<ql || qr<l) {
        return 0;
    }
    if(ql<=l && r<=qr) {
        return root->val[bit];
    }
    int mid = (l+r)/2;
    return query(root->L,l,mid,ql,qr,bit) + query(root->R,mid+1,r,ql,qr,bit);
}

node *seg[N];
int a[N],color[N];
int mindex[2][N],dp[X][X];

int solveDp(int l,int r,int n) {
    if(l==n && r==n) {
        return 0;
    }
    int &ret = dp[l][r];
    if(ret!=-1) {
        return ret;
    }
    ret = 1000000000;
    if(l<n) {
        int curIndex = mindex[0][l];int val = l+1;
        int cost = 0;
        if(val+1<=n) {
            cost += query(seg[curIndex],1,n,val+1,n,0);
        }
        if(r<n) {
            cost += query(seg[curIndex],1,n,r+1,n,1);
        }
        ret = min(ret, cost + solveDp(l+1,r,n));
    }
    if(r<n) {
        int curIndex = mindex[1][r];
        int val = r+1;
        int cost = 0;
        if(val+1<=n) {
            cost += query(seg[curIndex],1,n,val+1,n,1);
        }
        if(l<n ) {
            cost += query(seg[curIndex],1,n, l+1,n,0);
        }
        ret = min(ret, cost + solveDp(l,r+1,n));
    }
    return ret;
}
void solve() {
    int n;
    scanf("%d",&n);
    seg[0] = newNode();
    init(seg[0],1,n);
    int pos[2] = {0,0};
    for(int i=1;i<=n*2;++i) {
        char c;scanf(" %c %d ",&c,&a[i]);
        if(c=='B') {
            color[i] = 0;
        } else {
            color[i] = 1;
        }
        mindex[color[i]][a[i]-1] = i;
        seg[i] = newNode();
        update(seg[i-1],seg[i],1,n,a[i],color[i]);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d\n",solveDp(0,0,n));
}
int main() {
    solve();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:107:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:112:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         char c;scanf(" %c %d ",&c,&a[i]);
                                         ^

Judge Result