QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#414785#6531. Base Station ConstructionafyWA 79ms9600kbC++202.8kb2024-05-19 18:26:292024-05-19 18:26:30

Judging History

你现在查看的是最新测评结果

  • [2024-05-19 18:26:30]
  • 评测
  • 测评结果:WA
  • 用时:79ms
  • 内存:9600kb
  • [2024-05-19 18:26:29]
  • 提交

answer

// Problem: C. Trading
// Contest: Codeforces - The 2023 Guangdong Provincial Collegiate Programming Contest
// URL: https://codeforces.com/gym/104369/problem/C
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) cerr << #x << " = " << x << endl
const int N = 5e5 + 10;
const int M = 1e6 + 10;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);

int tree[N<<2];
void update(int x,int l,int r,int p,int v){
    if(l==r){
        tree[x]=v;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid)update(x<<1,l,mid,p,v);
    else update(x<<1|1,mid+1,r,p,v);
    tree[x]=min(tree[x<<1],tree[x<<1|1]);
}
int query(int x,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return tree[x];
    }
    int res=1e9;
    int mid=l+r>>1;
    if(ql<=mid)res=min(res,query(x<<1,l,mid,ql,qr));
    if(qr>mid)res=min(res,query(x<<1|1,mid+1,r,ql,qr));
    return res;
}
ll inf=1e18;
void clear(int x,int l,int r){
	if(l==r){
		tree[x]=inf;
		return;
	}
	int mid=l+r>>1;
	clear(x<<1,l,mid);
	clear(x<<1|1,mid+1,r);
}
void solve(){
    int n;
    cin>>n;
    n++;
    clear(1,1,n);
    vector<int>a(n+1);
    for(int i=1;i<n;i++)cin>>a[i];
    a[n]=0;
    int m;
    cin>>m;
    vector<pair<int,int>>l(m);
    for(int i=0;i<m;i++){
        cin>>l[i].first>>l[i].second;
    }
    sort(l.begin(),l.end(),[&](auto x,auto y){
        if(x.second==y.second)return x.first<y.first;
        else return x.second<y.second;
    });
    vector<int>lst(n+1);
    int j=-1;
    int mn=0;
    int k=-1;
    for(int i=1;i<=n;i++){
        while(j+1<m&&l[j+1].second<i){
        	j++;
        	if(l[j].first>=mn){
        		mn=l[j].first;
        		k=j;
        	}
        }
        lst[i]=k;
        // cerr<<mn<<"\n"<<j<<"\n";
    }
    // for(int i=1;i<=n;i++)cerr<<lst[i]<<" ";
    // cerr<<"\n";
    vector<int>dp(n+1);
    for(int i=1;i<=n;i++){
		j=lst[i];
		if(j==-1)dp[i]=a[i];
		else dp[i]=query(1,1,n,l[j].first,l[j].second)+a[i];
    	// cerr<<i<<" "<<j<<" "<<dp[i]<< "!\n";
		update(1,1,n,i,dp[i]);
    	// cerr<<"^^\n";
    }
    // cerr<<"!!!!!!";
	cout<<dp[n]<<"\n";
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//freopen("debug.txt", "w", stderr);
    int t=1;
    cin>>t; 
    while(t--)solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

input:

2
5
3 2 4 1 100
3
1 3
2 4
5 5
5
7 3 4 2 2
3
1 4
2 3
4 5

output:

102
5

result:

ok 2 number(s): "102 5"

Test #2:

score: -100
Wrong Answer
time: 79ms
memory: 9600kb

input:

6201
12
88 78 46 95 84 98 55 3 68 42 6 18
19
6 9
10 11
12 12
8 11
8 12
2 3
2 3
1 5
9 9
7 8
6 11
2 4
12 12
2 4
2 9
7 10
8 8
1 7
6 11
5
76 27 48 66 61
2
1 4
3 5
8
64 81 20 6 86 9 4 55
1
7 7
9
1 43 18 81 11 22 9 61 83
14
5 6
2 6
5 8
1 4
9 9
9 9
7 7
2 5
8 9
5 6
4 8
5 8
9 9
6 6
10
66 41 84 7 80 31 22 96 ...

output:

141
48
4
126
303
141
23
170
159
139
153
194
136
89
230
93
287
89
124
130
148
27
1
193
194
93
239
303
236
150
177
57
46
18
24
66
83
160
108
62
35
122
156
81
115
138
54
242
126
28
171
86
311
244
262
87
302
81
86
173
30
129
75
91
90
179
81
224
142
154
77
111
194
247
211
53
66
17
213
101
308
137
177
24
...

result:

wrong answer 1501st numbers differ - expected: '2892330597', found: '1000000000'