Submission #1120160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120160		RSAMSD	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	36 / 100	354 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
int t = 0;
int const f = 3e4 + 10;
long long mod = 1e9 + 7;//998244353;
long long dp1[f][5];
long long dp2[f];
long long par[f];
long long a[f];
long long mmn =0;
pair<long long, long long> edges[f];
long long prefix[f];
vector<pair<long long,long long>>g[f];
vector<pair<int,int>>gg[f];
struct node {
	long long val = 0;
	long long lazy = 0;
};
struct trpel {
	long long v, u, bank = 0;
};
node segtree[f * 8];
bool B[f];
void redany() {
	ifstream fin;
	ofstream fout;
	fin.open("std.in");
	fout.open("std.out");
}
void build(int v , int l , int r){
	if(r==l){
		segtree[v].val = 1e9;
		return;
	}
	int mid = (r+l)/2;
	build(2*v+1,mid+1,r);
	build(2*v,l,mid);
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
void upd(int v, int l, int r , int pos, int val){
	if(r==l&&r==pos){
		segtree[v].val = val;
		return;
	}
	int mid = (r+l)/2;
	if(pos>mid){
		upd(2*v+1,mid+1,r,pos,val);
	}
	else{
		upd(2*v,l,mid,pos,val);
	}
	segtree[v].val = max(segtree[v*2].val,segtree[2*v+1].val);
}
long long q(int v, int tl , int tr , int l ,int r){
	if(tl>r||tr<l)return 0;
	if(tr<=r&&tl>=l){
		return segtree[v].val;
	}
	int mid = (tr+tl)/2;
	return max(q(2*v,tl,mid,l,r),q(2*v+1,mid+1,tr,l,r));
}
// void merge(int a , int b, int n, int id){
	// if(g[a].size()>g[b].size()){
		// swap(a,b);
	// }
	// for(int u:g[a]){
		// if(u<n&&!B[u]&&par[u+1]==b){
			// upd(1,1,n,u,id);
			// B[u]=1;
		// }
		// if(u>1&&!B[u-1]&&par[u-1]==b){
			// upd(1,1,n,u-1,id);
			// B[u-1] =1;
		// }
		// g[b].push_back(u);
		// par[u] = b;
	// }
// }
long long powmod(long long a, long long p, long long modd) {
	long long ans = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			ans *= a;
			ans %= modd;
			p--;
		}
		if (p == 0)break;
		a *= a;
		a %= modd;
		p /= 2;
	}
	return ans;
}
long long tw = powmod(2, mod - 2, mod);
int main() {
	ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	//cin >> t;
	t = 1;
	for (int hhh = 1;hhh <= t;hhh++) {
		long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
		string s1;
		string s3;
		char s2;
		long double dec = 0;
		bool c = 1;
		priority_queue<pair<long long, long long>> qq;
		multiset<long long> mul;
		queue<long long> pp;
		map<pair<long long, pair<long long, long long>>, long long> conv;
		vector<long long> vec;
		cin >> n >> m;
		for(int i =0;i<m;i++){
			cin>>r>>l;
			for(int j = r+l;j<n;j+=l){
				g[r].push_back({j,(j-r)/l});
			}
			for(int j = r-l;j>-1;j-=l){
				g[r].push_back({j,(r-j)/l});
			}
			a[i] = r;
		}
		qq.push({0,a[0]});
		fill(dp2,dp2+n,1e18);
		dp2[a[0]] = 0;
		while(!qq.empty()){
			d = qq.top().second;
			qq.pop();
			if(B[d])continue;
			B[d]=1;
			for(auto u:g[d]){
				if(dp2[u.first]>dp2[d]+u.second){
					dp2[u.first] = dp2[d]+u.second;
					if(!B[u.first])
						qq.push({-dp2[u.first],u.first});
				}
			}
		}
		k = dp2[a[1]];
		if(dp2[a[1]]!=1e18)
			cout<<k;
		else
			cout<<-1;
	}
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:103:16: warning: unused variable 'mx' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                ^~
skyscraper.cpp:103:45: warning: unused variable 'k2' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                             ^~
skyscraper.cpp:103:60: warning: unused variable 'rr' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                            ^~
skyscraper.cpp:103:75: warning: unused variable 'll' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                           ^~
skyscraper.cpp:103:83: warning: unused variable 'lll' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                   ^~~
skyscraper.cpp:103:92: warning: unused variable 'rrr' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                            ^~~
skyscraper.cpp:103:101: warning: unused variable 'inf' [-Wunused-variable]
  103 |   long long n, mx = 0, d = 0, m = 0, k = 0, k2 = 0, r = 0, rr = 0, l = 0, ll = 0, lll = 0, rrr = 0, inf = 1e18;
      |                                                                                                     ^~~
skyscraper.cpp:106:8: warning: unused variable 's2' [-Wunused-variable]
  106 |   char s2;
      |        ^~
skyscraper.cpp:107:15: warning: unused variable 'dec' [-Wunused-variable]
  107 |   long double dec = 0;
      |               ^~~
skyscraper.cpp:108:8: warning: unused variable 'c' [-Wunused-variable]
  108 |   bool c = 1;
      |        ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 0 / 21
• Subtask 5: 0 / 43