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 ```