Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<stdio.h>
- #include<vector>
- #include<queue>
- using namespace std;
- typedef long long int ll;
- struct elem{
- int u;
- int h;
- bool wis;
- };
- int const N = 200010;
- vector<pair<int,int> > vec[N];
- int bsearch(int I,int high) //return idx where h = first at I
- {
- int L = 0,R = vec[I].size()-1;
- int idx;
- int h = high;
- while(L<=R){
- int m = (L+R)/2;
- int vh = vec[I][m].first;
- if(vh > h){
- idx = m;
- R = m - 1;
- }
- else if(vh < h){
- L = m + 1;
- }
- else if(vh == h){
- return m;
- }
- }
- return idx;
- printf("Bsearch error (%d,%d)\n",I,high);
- return -1;
- }
- int main()
- {
- freopen("input1.txt","r",stdin);
- int n,m,k;
- scanf("%d %d %d",&m,&n,&k);
- ll ban[n+1];
- int ans[n+1];
- for(int i = 1 ; i <= n ; i ++){
- scanf("%lld",&ban[i]);
- vec[i].push_back({0,0});
- ans[i] = -1;
- }
- for(int i = 1 ; i <= k ; i ++){
- int u,h;
- scanf("%d %d",&u,&h);
- vec[u].push_back({h,1});
- vec[u+1].push_back({h,-1});
- }
- int start;
- scanf("%d",&start);
- for(int i = 1 ; i <= k ; i ++){
- printf("Stick #%d : ",i);
- for(int j = 0 ; j < vec[i].size() ; j ++){
- printf(" (%d,%d)",vec[i][j].first , vec[i][j].second);
- }
- printf("\n");
- }
- // printf("%d -> %d",bsearch(4,10),vec[4][bsearch(4,10)]);
- // return 0;
- queue<elem> q;
- q.push({start,0,true});
- while(!q.empty()){
- int u = q.front().u;
- int h = q.front().h;
- bool wis = q.front().wis;
- printf("Test (%d,%d,%d)\n",u,h,wis?1:0);
- q.pop();
- int Hidx = bsearch(u,h);
- if(Hidx == -1)return -1;
- if(Hidx + 1 == vec[u].size()){
- ans[u] = (wis?0:1);
- continue;
- }
- if(wis){
- if(u-1 >= 1)q.push({u-1,h,false});
- if(u+1 <= n)q.push({u+1,h,false});
- }
- q.push({u + vec[u][Hidx+1].second , vec[u][Hidx+1].first , wis});
- }
- ll maxa = -1;
- bool iswis;
- for(int i = 1 ; i <= n ; i ++){
- if(ans[i] != -1){
- if(ban[i] > maxa){
- maxa = ban[i];
- iswis = ans[i] == 1;
- }
- }
- }
- printf("%lld\n%s",maxa,(iswis ? "USE" : "NO"));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement