codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1285.md (5748B)


      1 Source: https://codeforces.com/blog/entry/72950
      2 
      3 Tutorial is loading...
      4 
      5 **code**
      6 
      7 ```
      8 #include <bits/stdc++.h>
      9 using namespace std;
     10 #define finish(x) return cout << x << endl, 0
     11 #define ll long long
     12 
     13 int n;
     14 string s;
     15 
     16 int main(){
     17     ios_base::sync_with_stdio(0);
     18     cin.tie(0);
     19     cin >> n >> s;
     20     cout << n + 1 << endl;
     21 }
     22 ```
     23 
     24 Tutorial is loading...
     25 
     26 **code**
     27 
     28 ```
     29 #include <bits/stdc++.h>
     30 using namespace std;
     31 #define finish(x) return cout << x << endl, 0
     32 #define ll long long
     33 
     34 int n;
     35 vector <int> a;
     36 
     37 bool solve(){
     38     cin >> n;
     39     a.resize(n);
     40     for(auto &i : a) cin >> i;
     41     ll sum = 0;
     42     for(int i = 0 ; i < n ; i++){
     43         sum += a[i];
     44         if(sum <= 0) return 0;
     45     }
     46     sum = 0;
     47     for(int i = n - 1 ; i >= 0 ; i--){
     48         sum += a[i];
     49         if(sum <= 0) return 0;
     50     }
     51     return 1;
     52 }
     53 int main(){
     54     ios_base::sync_with_stdio(0);
     55     cin.tie(0);
     56     int T;
     57     cin >> T;
     58     while(T--){
     59         if(solve()) cout << "YES\n";
     60         else cout << "NO\n";
     61     }
     62 }
     63 ```
     64 
     65 Tutorial is loading...
     66 
     67 **code**
     68 
     69 ```
     70 #include <bits/stdc++.h>
     71 using namespace std;
     72 #define finish(x) return cout << x << endl, 0
     73 #define ll long long
     74 
     75 ll x;
     76 
     77 int main(){
     78     ios_base::sync_with_stdio(0);
     79     cin.tie(0);
     80     cin >> x;
     81     vector <ll> f;
     82     for(ll i = 2 ; i * i <= x ; i++){
     83         if(x % i == 0){
     84             ll cur = 1;
     85             while(x % i == 0){
     86                 x /= i;
     87                 cur *= i;
     88             }
     89             f.push_back(cur);
     90         }
     91     }
     92     if(x > 1) f.push_back(x);
     93     int n = f.size();
     94     ll ansa = 1e18, ansb = 1e18;
     95     for(int i = 0 ; i < (1 << n) ; i++){
     96         ll a = 1, b = 1;
     97         for(int j = 0 ; j < n ; j++){
     98             if((i >> j) & 1) a *= f[j];
     99             else b *= f[j];
    100         }
    101         if(max(a, b) < max(ansa, ansb)){
    102             ansa = a;
    103             ansb = b;
    104         }
    105     }
    106     cout << ansa << " " << ansb << endl;
    107 }
    108 ```
    109 
    110 **easier implementation**
    111 
    112 ```
    113 #include <bits/stdc++.h>
    114 using namespace std;
    115 #define finish(x) return cout << x << endl, 0
    116 #define ll long long
    117 
    118 ll x;
    119 
    120 ll lcm(ll a, ll b){
    121     return a / __gcd(a, b) * b;
    122 }
    123 int main(){
    124     ios_base::sync_with_stdio(0);
    125     cin.tie(0);
    126     cin >> x;
    127     ll ans;
    128     for(ll i = 1 ; i * i <= x ; i++){
    129         if(x % i == 0 && lcm(i, x / i) == x){
    130             ans = i;
    131         }
    132     }
    133     cout << ans << " " << x / ans << endl;
    134 }
    135 ```
    136 
    137 Tutorial is loading...
    138 
    139 **code**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143 using namespace std;
    144 #define finish(x) return cout << x << endl, 0
    145 #define ll long long
    146 
    147 int n;
    148 vector <int> a;
    149 
    150 int solve(vector <int> &c, int bit){
    151     if(bit < 0) return 0;
    152     vector <int> l, r;
    153     for(auto &i : c){
    154         if(((i >> bit) & 1) == 0) l.push_back(i);
    155         else r.push_back(i);
    156     }
    157     if(l.size() == 0) return solve(r, bit - 1);
    158     if(r.size() == 0) return solve(l, bit - 1);
    159     return min(solve(l, bit - 1), solve(r, bit - 1)) + (1 << bit);
    160 }
    161 int main(){
    162     ios_base::sync_with_stdio(0);
    163     cin.tie(0);
    164     cin >> n;
    165     a.resize(n);
    166     for(auto &i : a) cin >> i;
    167     cout << solve(a, 30) << endl;
    168 }
    169 ```
    170 
    171 Tutorial is loading...
    172 
    173 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    174 
    175 **code (pikmike)**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179 
    180 #define forn(i, n) for (int i = 0; i < int(n); i++)
    181 #define x first
    182 #define y second
    183 
    184 using namespace std;
    185 
    186 const int INF = 2e9;
    187 
    188 typedef pair<int, int> pt;
    189 map<int, int> ls;
    190 
    191 int get(vector<pt> a){
    192 	int cnt = 0;
    193 	int l = -INF, r = -INF;
    194 	sort(a.begin(), a.end());
    195 	forn(i, a.size()){
    196 		if (a[i].x > r){
    197 			if (r != -INF)
    198 				ls[l] = 0;
    199 			++cnt;
    200 			l = a[i].x, r = a[i].y;
    201 		}
    202 		else{
    203 			r = max(r, a[i].y);
    204 		}
    205 	}
    206 	ls[l] = 0;
    207 	return cnt;
    208 }
    209 
    210 void process(vector<pair<int, pt>> &qr, vector<int> &ans){
    211 	set<int> open;
    212 	forn(i, qr.size()){
    213 		vector<int> op, cl;
    214 		int j = i - 1;
    215 		while (j + 1 < int(qr.size()) && qr[j + 1].x == qr[i].x){
    216 			++j;
    217 			if (qr[j].y.x == 1)
    218 				op.push_back(qr[j].y.y);
    219 			else
    220 				cl.push_back(qr[j].y.y);
    221 		}
    222 		if (open.size() == 1 && !op.empty()){
    223 			++ans[*open.begin()];
    224 		}
    225 		for (auto it : op){
    226 			open.insert(it);
    227 		}
    228 		for (auto it : cl){
    229 			open.erase(it);
    230 		}
    231 		i = j;
    232 	}
    233 }
    234 
    235 void solve(){
    236 	int n;
    237 	scanf("%d", &n);
    238 	vector<pt> a(n);
    239 	forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
    240 	
    241 	vector<pair<int, pt>> qr;
    242 	forn(i, n){
    243 		qr.push_back({a[i].x, {1, i}});
    244 		qr.push_back({a[i].y, {-1, i}});
    245 	}
    246 	sort(qr.begin(), qr.end());
    247 	
    248 	vector<int> ans(n, 0);
    249 	ls.clear();
    250 	int cur = get(a);
    251 	
    252 	process(qr, ans);
    253 	forn(i, n) if (ls.count(a[i].x)) ++ls[a[i].x];
    254 	forn(i, n) if (ls[a[i].x] == 1) --ans[i];
    255 	
    256 	printf("%d\n", *max_element(ans.begin(), ans.end()) + cur);
    257 }
    258 
    259 int main(){
    260 	int tc;
    261 	scanf("%d", &tc);
    262 	forn(i, tc)
    263 		solve();
    264 }
    265 ```
    266 
    267 Tutorial is loading...
    268 
    269 **code (mohammedehab2002)**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 using namespace std;
    274 #define MX 100000
    275 int arr[100005],u[MX+5],cnt[MX+5];
    276 vector<int> d[MX+5];
    277 bool b[MX+5];
    278 int coprime(int x)
    279 {
    280 	int ret=0;
    281 	for (int i:d[x])
    282 	ret+=cnt[i]*u[i];
    283 	return ret;
    284 }
    285 void update(int x,int a)
    286 {
    287 	for (int i:d[x])
    288 	cnt[i]+=a;
    289 }
    290 int main()
    291 {
    292 	for (int i=1;i<=MX;i++)
    293 	{
    294 		for (int j=i;j<=MX;j+=i)
    295 		d[j].push_back(i);
    296 		if (i==1)
    297 		u[i]=1;
    298 		else if ((i/d[i][1])%d[i][1]==0)
    299 		u[i]=0;
    300 		else
    301 		u[i]=-u[i/d[i][1]];
    302 	}
    303 	int n;
    304 	scanf("%d",&n);
    305 	long long ans=0;
    306 	for (int i=0;i<n;i++)
    307 	{
    308 		int a;
    309 		scanf("%d",&a);
    310 		ans=max(ans,(long long)a);
    311 		b[a]=1;
    312 	}
    313 	for (int g=1;g<=MX;g++)
    314 	{
    315 		stack<int> s;
    316 		for (int i=MX/g;i>0;i--)
    317 		{
    318 			if (!b[i*g])
    319 			continue;
    320 			int c=coprime(i);
    321 			while (c)
    322 			{
    323 				if (__gcd(i,s.top())==1)
    324 				{
    325 					ans=max(ans,1LL*i*s.top()*g);
    326 					c--;
    327 				}
    328 				update(s.top(),-1);
    329 				s.pop();
    330 			}
    331 			update(i,1);
    332 			s.push(i);
    333 		}
    334 		while (!s.empty())
    335 		{
    336 			update(s.top(),-1);
    337 			s.pop();
    338 		}
    339 	}
    340 	printf("%I64d",ans);
    341 }
    342 ```